Great advice, I'd also add a couple more things about checking the desktop environment because its much more likely a windows or osx box was compromised and keys stolen or keystrokes captured than someone brute-forcing sshd or finding some sshd zero-day.

The few times we've been in this position, its always been someone's desktop that's been compromised. If you don't have a strong desktop security policy, a UTM, traffic inspection, key encryption policy, etc and you store keys or passwords locally, then this becomes a risk.