If I change the root password on a linux server, can someone still access root if they created an SSH authorized_key for root user?

I'm not even sure if I asked that right. Anytime someone mentions changing the root password, they mention changing /etc/passwd, or just using the passwd command, but I've never heard of having to change it in an authorized_keys file as well. Where might I find that, and how can I safely delete an entry or change this for root without causing havoc? Thanks!

Yes. You'll need to delete the user's public SSH key to completely remove access. If you're simply trying to remove one user's access to root it's a little tricky. Hopefully you've been using separate private keys, because otherwise you'll have to recreate the file and redistribute the public keys to the authorized users.

To remove the entry, you need to edit the authorized_keys file. If this is your root user on a Linux box, chances are the the file can be found at /root/.ssh/authorized_keys. You'll need to remove the line that contains the public key of the user that you're removing. Unfortunately, there's no easy way to know what line this is without a copy of that user's public key.

Yes; it's considered bad practice to allow people to ssh in as "root" for just this reason. Your boxes should probably have root's ssh disabled, and use something like "sudo" to provide access controls over who can do what as root, that way you won't need to give out the root password or anything equivalent.

Leavers' accounts can simply be disabled and you can guarantee that they can't get back in (unless of course, they've left some back doors, which is something you can't do anything about anyway).

We use an ldap directory to store users, groups and ssh keys, then restrict "sudo" access by group.