Chinese hacking attempt/Secure your Servers

I just have reinstalled Debian 7 on my VPS. Logged in for the first time with "root" and on port 22..then I didn't locked down anything and within an hour I can see the below root password breaking attempt in /var/log/auth.log file .. WHOIS shows its an Chinese IP. God knows when these people will get rid of Script kiddies. Now I have locked down my VPS... does anybody else have similar story and what best steps you took to Secure your Servers .??

Jan 24 02:28:30 Sputnik sshd[1566]: pam_unix(sshd:auth): authentication failure; logname= uid=0 euid=0 tty=ssh ruser= rhost=222.189.239.126 user=root Jan 24 02:28:32 Sputnik sshd[1566]: Failed password for root from 222.189.239.126 port 1616 ssh2 Jan 24 02:28:35 Sputnik sshd[1566]: Failed password for root from 222.189.239.126 port 1616 ssh2 Jan 24 02:28:37 Sputnik sshd[1566]: Failed password for root from 222.189.239.126 port 1616 ssh2 Jan 24 02:28:39 Sputnik sshd[1566]: Failed password for root from 222.189.239.126 port 1616 ssh2 Jan 24 02:28:41 Sputnik sshd[1566]: Failed password for root from 222.189.239.126 port 1616 ssh2 Jan 24 02:28:43 Sputnik sshd[1566]: Failed password for root from 222.189.239.126 port 1616 ssh2 Jan 24 02:28:43 Sputnik sshd[1566]: Disconnecting: Too many authentication failures for root [preauth] Jan 24 02:28:43 Sputnik sshd[1566]: PAM 5 more authentication failures; logname= uid=0 euid=0 tty=ssh ruser= rhost=222.189.239.126 user=root Jan 24 02:28:43 Sputnik sshd[1566]: PAM service(sshd) ignoring max retries; 6 > 3