Part of the problem here is that the default constructor creates a new key
pair.
RSA key paris are created through horrendous algorithms, because they are
huge complimentary prime numbers with certain relationships (well, that's a
rather simplistic view, but you get the idea).
What .NET hides from you (you'd be dealing with this explicitly if you were
using the Crypto API) is that key containers and keys are managed by CSPs
(crypto service providers). These are C DLLs that conform to certain
standards to produce cryptographic functions. On older machines, you have
very antiquated providers, while on machines like XP, you'll have newer
providers installed. Then, you can also have additional providers installed
because of other software on the machine. What this means is that you likely
have a weak provider on the old machines and a much stronger provider on the
XP machine - or, the provider might be configured differently. A weak
provider that has RSA capabilities will probably create a 512 bit key. By
contrast, a stronger one will create an RSA key of at least 1024 bits. The
bigger the key, the longer the algorithm takes, obviously. And the growth,
in my experience is more than exponential.

So, what you might want to do is use the constructor that specifically takes
a key size.

RSACryptoServiceProvider p = new RSACryptoServiceProvider(1024);

If that is still slow, try using the constructor that takes a CSPParameter
instance, and you can specifically set a provider and compare that to with
the other machines using the same provider. Again, be careful because older
versions of Windows don't always have the same providers as newer versions
(for example, i doubt 98 supports the Enhanced RSA and AES provider).

-Rob Teixeira [MVP]