They got the first 103 keys with batch GCD. After that, they found many more keys by looking at patterns in the keys and doing trial division by keys that were similar to the patterns. A better PRNG would make that harder (to reverse-engineer the patterns in the seed) and a slower PRNG makes it slower.
A better (i.e., not completely utterly horribly broken) PRNG would have made it impossible to observe and associate patterns in the output, even with poorly seeded entropy. There's no reason such a PRNG needs to be any slower than a fast cipher or hash function such as AES or SHA-2.
