What's better - Fail2ban or change port?
Then port change, SSH hardening in general (key + pass, google pam auth module, etc), then fail2ban, denyhosts, sshguard, tallow, etc.
And all that doesn't matter if you don't see any alerts. Need a hids (I like OSSEC) and a good logging system for syslog etc alerts.
Number one issue I see with servers (besides badly secured in the first place), is a bunch of logs no one ever actually looked at.
That leaves port change, which is better than nothing. But even better than that is proper firewalling with whitelisted IPs.
If password authentication is a must then hopefully you can still go for 2FA (there's a few two factor authentication plugins for PAM). But if you do that then make sure you also stick fail2ban in there as well.
I think nobody argues that it adds security. The problem is that:
1. It adds very little security: 16 bits is not much, and the result is not 256 bits (say) of SSH key plus 16 bits equals 272 bits, but instead effectively still 256 bits, or 256+8×10⁻⁷³ bits.
2. The security it adds is itself bad (sent in cleartext, easily brute-forced)
3. These problems stand against the many drawbacks of this previously discussed (complexity, confusion, etc.).
And the final argument: If increased security is what you want, simply increase your key lengths and/or password lengths, and you will get much more than 8×10⁻⁷³ bits of security, without any of the above problems.
I am not in a position where I feel I need to worry about remotely exploitable 0-days in my SSH daemon. If you are, then your situation is, I feel, exceptional.
That said, perhaps those people should sponsor a project to fix this for real. This could be accomplished by having not one program, but two, one after the other, both with realistic keysizes and security. The password/key to get log in would be then be the combination of two separate keys, one for each program.
But what I have described is more or less the same as having a key/password-protected tunnel on top of SSH, so they could just use that. A 0-day in the tunnel/VPN would not allow access through SSH, and a 0-day in SSH would not matter since SSH can’t be accessed directly in the first place. This way, both the tunnel and SSH would need a 0-day at the same time for the security to fail. Like a RAID-1 array. If even this is not sufficiently secure, just increase the number of layers.
I'm also not really a fan of leaving things with a shell connection on the net, again part of configuration. If you can root the ssh server, you could likely root a vpn box.
Also, I guess, I'm sorry, you're not allowed to ask questions on HN anymore. Thanks for the drive by down vote.