I'd say there's no way key generation could take as short. On 200+MHZ PCs it takes up to a minute (depending on key size obviously...) so no way a '51 could do this in reasonable time for reasonable (512bit) key size.

As to encryption - depends on key size and on amount of data to encrypt. From my experience a PC like the above with PGP takes about 3s to encrypt "your average email" with a 1024bit key, so for a 8-bit '51 without FPU, with 256 bytes of internal RAM (consider 3-10 cycles to fetch a desired byte from XRAM) and such, 1 second per character encrypted sounds like a safe bet.