Here is a logentry, which was executed:
mkdir /root/.ssh/;echo "ssh-rsa <some unkown public-key> > /root/.ssh/authorized_keys
I'm guessing that I was hacked. Any advice for cleaning up (except password change, cleaning of authorized keys)?
If the machine was compromised, you can not trust anything on it, period. The only sane course of action is to disconnect from the network, do a full backup using a rescue system (probably install media for your system doubles for that). Then install from scratch, making sure you have everything up to date and properly secured. Change all passwords, even irrelevant ones, also passwords for remote sites you used from this computer. If you need some data, store it away and check it carefully before letting it anywhere near the computer again.
You might want to save the original disk (or an image) for forensic fun...