Sounds like you are being hit by brute force SSH attacks- UGLY.
I have overcome this by creating a pptp tunnel first then logging in locally. This way Port 22 is not open to the world. Upside is that I am not confined to any particular IP, down side is that I cannot walk into any Internet Cafe and just connect. (because it is the wrong IP or that the PPTP connection is not set up already) Also requires whatever device is on the border to supports pptp pass thru.
Open VPN is good if the device doesnt support PPTP pass as the OpenVPN port can be forwarded. Once again, I dont expect to walk into a cafe anywhere and find an open vpn client sitting there waiting for me !!
Changing the SSH port to something like 222 or 2222 is probably the best option but than can have its own set of issues if the client is behind a firewall.
I have also seen in the forums some smart iptable rules which will block all traffic from a specified ip for a specified time, say 24hrs, after x number of failed logins with y seconds. (Search these forums for Snort-Guardian)
There are options, they all have their pro's and con's. What works for one person may not for another. The challenge is finding the one that works for YOU !. Of course, if you are confident your passwords a strong enough, you can just let them keep knocking on the door.
Rgds
Peter