Slow site == attack

I help run a few websites and saw one was running slow today. I jumped on the server and ran top, to no avail. The hosting provider had locked it down so I fell back on my sys admin days and did the next best thing: tail -f /var/log/messages:

Jun 9 20:28:56 ysdc sshd(pam_unix)[12973]: check pass; user unknown
Jun 9 20:28:56 ysdc sshd(pam_unix)[12973]: authentication failure; logname= uid=0 euid=0 tty=ssh ruser= rhost=pool-71-182-88-2.ptld
or.fios.verizon.net
Jun 9 20:28:59 ysdc sshd(pam_unix)[12975]: check pass; user unknown
Jun 9 20:28:59 ysdc sshd(pam_unix)[12975]: authentication failure; logname= uid=0 euid=0 tty=ssh ruser= rhost=pool-71-182-88-2.ptld
or.fios.verizon.net
Jun 9 20:29:02 ysdc sshd(pam_unix)[12979]: check pass; user unknown
Jun 9 20:29:02 ysdc sshd(pam_unix)[12979]: authentication failure; logname= uid=0 euid=0 tty=ssh ruser= rhost=pool-71-182-88-2.ptld
or.fios.verizon.net
Jun 9 20:29:05 ysdc sshd(pam_unix)[12984]: check pass; user unknown
Jun 9 20:29:05 ysdc sshd(pam_unix)[12984]: authentication failure; logname= uid=0 euid=0 tty=ssh ruser= rhost=pool-71-182-88-2.ptld
or.fios.verizon.net

This repeated itself approximately 2900 times in the log. Brute force attack. Suspecting what was up, I did a netcat connection to port 22 on the attacking host and confirmed my suspicion:

SSH-2.0-OpenSSH_4.7p1 Debian-8ubuntu1.2

Looks like the kiddies are out doing their brute force of the OpenSSH Debian keys attack from a few weeks ago. Make sure you have your machines patches and re-keyed!

EDIT: Here's a breakdown of the hosts performing SSH brute force attacks since yesterday:

7202 rhost=210.118.178.184
5601 rhost=72.249.190.130
2898 rhost=pool-71-182-88-2.ptldor.fios.verizon.net
1235 rhost=220.225.200.185
364 rhost=190.9.128.108
139 rhost=61.7.150.74
52 rhost=pe26501.lrdns.com