Another simple configuration that helps is to pick a random high port for ssh. Now, please don't say that this is false security or "security through obscurity". Yes, a port scan will show the ssl running on the port and a motivated attacker would do the port scan first. But most of these bot type attacks don't bother with the port scan. They randomly try port 22.
I run snort and OSSEC on the ssh server. I have had this set up for about nine months never had a "user authentication failed" (that wasn't me mistyping my password ;)) whereas I have had 547 distinct IP addresses attempt to connect to port 22. So, for the little effort that is involved in setting up ssh on a random high port, the fact that is makes me less of a target to the bot attacks is well worth it.
(BTW, I make sure I use a port that is not in nmap's list of known ports. That way, someone who does an nmap scan without specifying specific ports will not scan my ssh port. nmap scans it's list of known port NOT all ports, unless you tell it otherwise. Again, not perfect but may keep a script-kiddie or two at bay...)