I'm totally sure the RSA operations are using the AES instructions
> Try using your old 2003-era system to generate keys again and tell us how fun it is.
generating (fresh) rsa keys? you don't do that on connection to a SSH server
as for what actually happens on connect, 2004 laptop: 33 signatures/second and 2200 verifications/second (+DH/ECDH)
the RSA operation (verifying the server's host key) took a total of 0.0005s
even my raspberry pi 1 can do 240 4096-bit verifications/s and several thousand ECDH's/second
and I have yet to see a SSH server with 4096-bit host keys
tldr: even old computers are fast (and data > supposition)