This looks weird. An anemic laptop from 2005 generates 4096-bit RSA keys (i.e. huge, overkill keys) in less than 10 seconds. "Several minutes" would indicate that there is something wrong in your system. Or that you are aiming for ridiculously large RSA keys (2048 bits are very fine; 3072 bits are understandable if you have paranoiac managers or must comply with some equally paranoiac regulations; 4096 bits are over-the-top exaggerated; beyond is just plain stupid, and will also incur interoperability issues).
In any case, RSA key pair generation mostly consists in producing two random prime numbers of about half the target modulus size. Generating a prime number boils down to, mostly, trying random odd integers until a prime one is found. This is amenable to high parallelism, although it rarely matters.
One must say that generating RSA keys securely requires some good knowledge of mathematics and cryptography. There are many RSA keys out there, which were produced from poor PRNG and are, therefore, highly breakable -- and it cannot be tested. I therefore strongly urge you to reconsider fiddling with such code.
Finding out why it takes several minutes on your machine is more important.