The dilemma of ssh authorized_keys key files and its comments

Imagine the following situation: You care for live servers and work in a team of let’s say five, six or even more people. Access to the servers is granted through ssh. The people login either as root (yes, you should not do that, but that is not the point here) or as user with sudo rights or they just share an unprivileged account. Authentication is done via ssh keys.

Now somebody leaves your team. Either as he has a new job or he just got fired. Of course you start deleting his key from all those ~./ssh/authorized_keys files. You have been smart before as you forced your buddies to use their real name or mail address as comment in the key. Easy identification.

But then you start thinking: How do I know I am deleting the right keys? Let’s say the target user is a smart bad guy. He just might have done the following: He looks for somebody who seldomly logs in. Maybe a manager has a key just for security purposes or something like that. Now he exchanges the order of the keys and its comments if they are in a shared authorized_keys or he even exchanges the authorized_keys files when they belong to different users, so you just think you are deleting the right keys but disable another person – in the worst case even yourself.

Of course you can start working around this with trip wire, shell scripts and so on, but be honest: Being able to change the comment in an ssh key without disturbing a checksum or even a signature that rings bells and whistles is a pain for every security minded administrator.

Feel free to hint me an easy solution for this that you might already have implemented.