I firewall off the SSH port for one minute after 4 unsuccessful logins in one minute:

    -A SSH_CHECK -m recent --set --name SSH --rsource 
    -A SSH_CHECK -m recent --update --seconds 60 --hitcount 4 --name SSH --rsource -j REJECT --reject-with icmp-port-unreachable 
    -A SSH_CHECK -p tcp -m tcp --dport 22 -j ACCEPT 

This is in addition to default REJECT for everything that I don't explicitly allow.

(Incidentally, the kernel I'm running doesn't support this for ipv6 addresses... so you can bruteforce my ssh server over ipv6 for as long as you want. But fortunately, it's hard to automatically scan the entire ipv6 address space :)