What to do when someone logged as root on my server

Solution 1:

I believe this is a bug That has been hanging around for far too long which is fixed in later versions (6.0p1).

It should be fairly easy to verify this by trying to connect to the system yourself from a host that would be restricted, using a different key and seeing what messages you get.

Solution 2:

This might be a long-standing bug in OpenSSH which was only fixed in 6.0p1. In that case you can safely ignore it. However, if you want to be safe, the original answer (assuming you aren't affected by this bug) is:

Your ssh private keys have likely been compromised, since someone had a valid private key for logging into your root account. The fact that someone didn't log in from a permitted IP address saved you from further compromise. Nevertheless, this is a significant compromise; it suggests that your workstation (or other machine you typically work from) was compromised.

You should treat every workstation and server you touch as potentially compromised. Format and reinstall your workstation(s). Revoke/destroy all of your existing ssh keys and rekey everything. Change all passwords. Strongly consider wiping and reinstalling any servers on which you have access to log in with this key.