Not disagreeing, but I think both randomness and primality testing both have the problem that it's so easy to do them poorly. Generating random primes of these sizes isn't all that difficult, and even proofs can be done in reasonable time frames (e.g. under 10 seconds for 1024-bit inputs). There are also a couple random proven prime algorithms which run pretty fast. Getting software to correctly implement everything .... that seems to be hard.
> Getting software to correctly implement everything .... that seems to be hard.
Exactly. Generating random primes is not terribly difficult in theory, but in practice it is very tricky, which makes it hard to answer the question: how do you know you can trust your keys? Sure, you can verify that your primes are prime, but how do you know how much entropy they have? The only way to figure that out is the audit the code. (And then you have the problem of making sure that the code you're running is the code you audited.)
Generating random numbers is also tricky, but a lot less so than generating random primes: take an entropy source and run it through a whitener, i.e. feed it to sha512. As long as you have a reliable estimate of the lower bound of the quality of your entropy source, you're good. A lot fewer moving parts.
