The ordering is not random; in fact, it's very simple. Alphabetize the four teams in a division--e.g., Arizona, S(ain)t Louis, San Francisco, Seattle; Denver, Kansas City, Oakland, San Diego. Split them into pairs, call the first pair A and the second pair B. A team will always play both the "A" teams in another division on the road, and both "B" teams at home, or vice versa; the next time the divisions meet, they'll reverse it (guaranteeing a home-and-home series at least every six years in conference, and eight years between conferences). Unfortunately, it just so happens that the "B" teams in both divisions are on the coast, and the "A" teams are both inland.
So each AFC East team has to play both SD and OAK on the road once every six years, and has to play both SEA and SF on the road once every eight years--so the four West Coast trips happen once every 24 years. The good news is that the JEST are in the same boat as the Pats. The better news is that, assuming the current rotation continues unchanged, it won't happen again until 2032.