RSA with 65536-bit keys is quite secure, but it's hugely impractical. Try it in OpenSSL. Key generation alone will take you several hours on a fast, current-generation machine.
At the 64kbit-level (again, BIG BIG difference from 16kbit), even the cost of encryption/decryption alone is easily going to cripple a high-traffic server.
Google does use ECC, on platforms that support it. See for example http://googleonlinesecurity.blogspot.com/2011/11/protecting-... which has a screenshot.