Also, are operations linear in key size? This source says for k bits in a key, operations with the private key are cubic in key length, and key generation is O(k^4):
They are significantly slower. But for GPG it doesn't matter, as long as time is reasonable. It uses RSA to encrypt short key which then encrypts the entire message using something like AES. But it would matter for website served over HTTPS.
http://x5.net/faqs/crypto/q9.html
but seems to be from the 90s. Maybe faster algorithms are merited now...