The existence of that K9 clique shows that public-key cryptosystems have gone to the dogs (sorry, bad pun!).
There is no reason to make a distinction between "really bad" (two identical keys) and "really, really bad" (two keys with a prime gcd). Both cases should be considered as completely insecure.
The latter is more insecure, since *anyone* could easily use Euclid's algorithm (which takes at most O(n²) time for n-digit keys) to obtain the common factor, then deduce the other factor by division (also O(n²), using the naive method). If a key is merely really bad, then only people sharing the key could factorise.
The title suggests that the solution is to switch from RSA to a single-secret system, whereas the actual solution is to make sure your random generator is in working order.
Agreed. An amenable solution is to seed a PRNG with an online source of pure random information (there is a quantum random bit generator, where the CAPTCHA is an advanced calculus problem, apparently). Once the random integer has been generated, it is fairly trivial to count upwards until a probable-prime is obtained (and, at those magnitudes, Fermat pseudoprimes are sufficiently sparse to ignore them completely). Sincerely, Adam P. Goucher