Anyways, everyone I know, gets a dictonary bomb every few days or so (either on the password, or looking for users with weak or no passwords)
Several things to lock this down.
1. Disable root access over ssh. Once logged in with a wheel account, use SU and SUDO to get things done.
2. Ensure that only accounts that need to be logged in via ssh have valid shells. Otherwise point them to nonexistant shells.
There's more especially with firewalls but security is a tricky thing.
Anyways, I found a perl script/cron job that will temporaily ban IP addresses from accessing sshd after n failed logins.
Setting this up is good and bad for security. It becomes possible to DoS the machine by spoofing IP addresses, but as the majority of these attacks are script kiddies or bot nets I'm not to worried about it. Also since it's trivial for me to hook up a keyboard and monitor to the little machine, regaining control and clearing out the DoS spoof is a trivial matter. If your boxes are crosscountry at a colo, you may wish to reconsider this.