Just put sshd on a nonstandard port, and 95% of the traffic goes away. Vandals can't be bothered with port-scanning, probably because the risk of getting banned before the scan is even complete is too high.
But I agree that keys are not optional anymore.