This stared as a comment on freedom_is_chaos's answer, but grew too large...
@Meder: Other services, such as SSHd itself, keep logs - not just Apache. Though any well coded exploit (or an exploit created by a good quality off-the-shelf-exploit-generator) will probably cove its tracks once it gets in.
A poorly chosen password for root or an account that has sufficient privileges via sudo is the most likely attack vector here, given the exploit is making many SSH connections (to try spread itself to other servers the same way it infected yours). You need to stop the VM immediately. The longer it is up the longer it is a problem, potentially causing further infections.
If you have any data on the VM that you want to keep still shut it down immediately - don't mess around taking backups first because unless things have changed since I last use Linode's services you can create a fresh, unexploited, VM and attach the old drive to it to pull data off. Be careful not to trust that data, especially executable binaries and scripts, though - double check anything you use in case it has been modified to make future exploits easier (you don't want to accidentally copy into the new VM a back-door that was installed into the old one).
Also give the page linked to by tasaro a read. That looks like a good summary of how to try secure a simple VM. If you will not (can not for some reason) use key-based authentication at least use strong passwords - don't worry about them being memorable, as you can store them in something like keepass instead of needing to remember them (just make sure you keep your keepass daatase in a safe). While a remote exploit could easily get to something like "elephant4" via a dictionary based brute-force guess it is unlikely to hit upon something like "eGz3nk7aVdN7OIChoPy7". Also make sure that you use different passwords for different services - that way if one manages to slip out somehow you only compromise one service not many others too.
