WHM/Centos/VPS Having Brute Force Attacks

I am getting these types of reports in my nightly reports:

=================
sshd:
Authentication Failures:
unknown (bips131.bi.ehu.es): 212 Time(s)
mail (bips131.bi.ehu.es): 4 Time(s)
news (bips131.bi.ehu.es): 4 Time(s)
root (bips131.bi.ehu.es): 4 Time(s)
unknown (swplinux02.swp.ewr.qwest.net): 1 Time(s)
Invalid Users:
Unknown Account: 213 Time(s)

Two nights ago:

--------------------- pam_unix Begin ------------------------

sshd:
Authentication Failures:
unknown (195.251.109.21): 413 Time(s)
root (195.251.109.21): 108 Time(s)
webadmin (195.251.109.21): 18 Time(s)
root (200.55.193.59): 16 Time(s)
daemon (195.251.109.21): 8 Time(s)
ftp (195.251.109.21): 5 Time(s)
root (218.19.69.193): 4 Time(s)
Invalid Users:
Unknown Account: 413 Time(s)
===============

My VPS support said I could try:

-alternate sshd port
-require key access
-selecting client ip access
-rate limit incoming sshd syn packets per src address

However, I need some help understanding the best way to address these so that these brute force attacks aren't successful.