Dealing with automated SSH password-guessing

We run a number of servers on Amazon EC2 (in their Ireland region) and I see roughly 3000 failed login attempts per machine over ssh (thankfully we have been using public-keys since we begun to use Linux back in the day). For the physical servers that we have I see roughly 200 tries per server for the servers located in Stockholm and roughly 600 for the servers located in London.

So yes the number of attempts is higher on places such as Amazon EC2.