It's likely that if he left that key in there with a valid e-mail address then whoever compromised the server wasn't trying to be discrete.  I would check my auth logs to see when/if someone was logging in from somewhere suspect.  Next if the server was compromised, it's done, you can never trust it again, no amount of clean up or post-mortem investigation can ever give reasonable confidence that there's no back door on it.  Move the services and data and make a new server/clean install, then look very carefully at what attack vector was exploited and close it (like if it was brute force you should have ssh for root turned off, more restrictive firewall rules and ssh guard).

Having a server compromised can be a huge headache, good luck.