The host was only accessible via private key or Linode's LISH shell. That's what seems most suspicious.

There is some minor evidence remaining in the .bash_history that is curious.

I'd be interested in a write-up about anything you find in that .bash_history or logs, would you consider writing one?

Here's the main bulk of the obviously bad things:

    3  ls
    4  ls -al
    5  chown syslog auth.log
    6  ls -al
    7  chown syslog kern.log
    8  ls -al
    9  chown syslog syslog
   10  ls -al
   11  echo -n '' > /media/xvda/root/.bash_history
   12  echo -n '' > /root/.bash_history
   13  echo -n '' > /root/.viminfo
   14  L=$(find /var/log -type f); for F in $L; do echo -n '' > $F; done
   15  rm -rf /etc/ssh/*_key* #remove host keys
   16  rm -rf /var/lib/dhcp/* # dhcp leases
   17  echo "echo 'options rotate' >> /etc/resolv.conf" > /etc/dhcp/dhclient-exit-hooks.d/rotate
   18  ls
   19  ls -al /var/log
   20  ls
   21  ls -al /var/log
   22  exit
   23  ls
   24  ls -al /var/log
   27  adduser in
   28  su - in
   29  vi /etc/sudoers
   30  vi /etc/gro
   31  vi /etc/group
   32  groupadd --help
   33  groups
   34  groupmod
   35  groupadd --help
   36  vi /etc/group
   37  su - in