Literally the first thing I do on any new machine is disable password logins, disable root logins and then punt the SSH port to the top of the range (usually 47999).

Every remote machine gets it's own keypair as well and links between machines also get their own key-pairs (key handling is PITA, I've yet to find a method I really like), Keys for work stuff are back up on multiple LUKS memory sticks (two in separate safes, two offsite).

I'm fortunate in that work machines are in the pet category not cattle category so we don't need to change keys that frequently (though I will rotate them out yearly anyway).