I couldn't say anything on the forensic side of things.
But regarding this:
Also there are things like - enabling your firewall, enabling selinux, removing unnecessary services, disabling remote ssh login using username and password and using crypyographic keys instead. Disabling root login via ssh. Installing something like fail2ban and setting it up to automatically block an IP after a set number of failed login attempts. Setting up some kind of intrusion detection system that will alert you if the system has been altered/compromised.
And those are just a few suggestions off the top of my head. I'm not even a sys-admin/server-guy.
I'm sure
@Rob,
@f33dm3bits and some of the other sys-admin types here can suggest additional courses of action to keep your machine secure when you re-install and set everything up again.
What kind of setup was this Debian PC? What services did you have running on it? Web server? SSH?