OpenSSH has a post-quantum hybrid algo using SNTRUPrime and ed25519.
> * ssh(1), sshd(8): Add experimental quantum-computing resistant
key exchange method, based on a combination of Streamlined NTRU
Prime 4591^761 and X25519.
True, in fact an elliptic key with 4096 bits would be way overkill. But there is also the issue of support.
Ed25519 and RSA3072 offer around 128 bits of entropy, which is kind of on margin even classically. RSA 4096 offers more protection against brute force, around 144 bits if I recall correctly. Of course, RSA is vulnerable to side channel attacks (though these nay not be in the threat model of many people).
You could use ed448 with 224 bits of security with still shorter keys than common RSA variants. But then it’s not supported in most places.
Is it though? It requires around 2^128 operations to be broken. It does not seem very marginal to me.
It is not like AES where you have to deal with batch-attacks or cryptographic hash functions where collisions for a n-length output require only sqrt(2^n) attempts.
The number of usable qubits in a single computation is expensive and has been growing slowly and until that changes I figure it's more likely to be surprised by a break of ed25519 but not RSA 4096 than to be surprised by a break of both.