We see this kind of question on ServerFault all the time. Unless you're a Past-Master Neckbeard, and unlikely to be so if you're asking this question, just nuke it and re-install. And next time lock down your install.
Here's some good ideas to start with on that front.
a) Good passwords. Don't use easily guessable passwords. In fact, avoid using dictionary words in your passwords at all. Mine's a nice long 20-character string that can't be guessed without brute force, and longer than most rainbow lists. It lives on a post-it note in my office and backed up in a USB key in the lockbox. If someone has physical access to your box, software security means just about nothing except how long it takes for them to get your data.
b) Certificates > Passwords. Tie your accounts to certificates instead of just passwords, and then disable Password-Only Authentication.
sshd_config: PasswordAuthentication no
c) Turn off root logins via SSH. This way that can't simply brute force your root account on your install. The AllowGroups or AllowUsers directive is your sshd_config is an excellent way to do this.
d) Lock down your open ports. Many distributions run a default ACCEPT policy. That means that any system that can route to your install will be able to initiate connections to any running service. Run a default REJECT and selectively enable services you want to be available. IPTables/Netfilter is the classic means of doing this. Some distributions some a GUI or "TUI" ASCII-GUI tool to manage this. Some, including the ones most often running ACCEPT ALL, have easier to use X/Windows GUI tools like UFW for Ubuntu.
e) Once you've done ALL these things, then consider something like Fail2Ban to rate limit SSH connections. Once a system makes a configurable number of failed connections, it can go in the penalty box for a defined period of time.
