For the tinfoil among us, jump on the post-quantum key exchange train, there's little overhead, it still uses traditional elliptic curve crypto, best of both worlds.
The jump-off: sntrup4591761x25519-sha512@tinyssh.org
sntrup761x25519-sha512@openssh.com
So if you add the previous one to your server config, sshd may fail to start after upgrading to 8.5 or newer (8.7 is the most recent release).
I started using sntrup4591761x25519-sha512@tinyssh.org about two years ago, and the new one when OpenSSH 8.5 came out. They've both worked flawlessly for me. Thank you to TinySSH and OpenSSH, and of course cryptographers, for making this possible.
I run tinysshd on some RedHat 5 servers, and I rely upon the latest post-quantum exchange. I also jack all my putty users into it with an agent, and I don't assign them passwords.
It would be nice if I was allowed to upgrade from RedHat 5, but I am not.
Despite being sidelined in NIST's post quantum standardisation project it's interesting to see their Streamlined NTRU Prime algorithm still being the main real world adoption out there right now. I'd be interested if anyone knows of a more utilised post-quantum algo irl.
Bullseye is still on 8.4. OpenSSH on Windows appears to be 8.1.
tinyssh does what the top comment comment in this thread suggests, and in fact goes further. It does not include bad algorithms. This is arguably better than only "deprecating" them.
All of today's practical public key crypto could be broken by a sufficiently powerful quantum computer - if one existed which today it does not - thanks to a trick called Shor's Algorithm.
However, there are new public key algorithms that aren't affected by Shor's algorithm. Two problems. 1. They're all worse, they have huge keys for example, or they're slow, so that sucks. 2. We don't know if they actually work, beyond that Shor's algorithm doesn't break them on hypothetical Quantum Computers.
Even if you decide you don't care about (1) and you're very scared of the hypothetical quantum computers (after all once upon a time the Atom Bomb was also hypothetical) you need to deal with (2).
Post-quantum schemes like this for SSH generally arrange that by doing two things, they have the shiny new Quantum Resistant algorithms, but they also have an old-fashioned public key algorithm, and you need to break both to break their security. Either alone won't help you.
That we know of. There are commercially available quantum computers [0] and there are roadmaps for commercial technology ramp up significantly [1]. Remember, that's a roadmap to projected commercial viability. It's hard to say what state actors are capable of right now.
[0]: https://azure.microsoft.com/en-us/services/quantum/
[1]: https://venturebeat.com/2020/12/09/ionq-roadmap-quantum-mach...