If anyone else has this issue please install fail2ban. It basically does a 'tail -f' on your logs and blocks addresses based on your rules. For example, if there are 6 failed login attempts in a 24/hour window, block them.
Be careful, though, I had it installed and blocked myself for a few minutes when mistyping my password. I've switched to SSH keys completely since, but be careful not to set too low a limit.
100% agree. We run some high traffic ssh bastion hosts with fail2ban. We use fail2ban, ip block white lists, and good syslog monitoring for easy troubleshooting.
I've had a lot of success with denyhosts. As a bonus, all of my machines with publicly facing SSH synchronize the generated ruleset.
How are you synchronising the ruleset? All I know is the option to publically sync, do you have a way to privately sync?