I think a better solution in the end is to generate a random password
for each box, and leave it, on paper, in a safe or similar. It's very
rare anyone needs to use it.
Here is a hint (joke), how to secure root password for servers that are physically accessible.
Just generate a random password during install long enough to be not able to remember it. Do not write it down, continue installation.
At any given time you need the root session, just get the disk drive from your server and connect it to another machine, then just replace the hash to one you know password for in /etc/shadow. Place your drive back and boot up. After you finish the work, change your root password again to some crazy piece of random.
;-)
Seriously, you have to trust someone to achieve goals. So accessing server via ssh keys is pretty normal and secure + ldaps auth of course (centralized account management), so if someone leaves, just disable his account. sudo supports ldap auth, kind of on group level, so if user even got into a server for some reason, he can't become root, because his account was deleted and not in sudo enebled group anymore.
After you configure the ldap and sudo for this scenario, just disable password auth and root login in ssh conf. Also setup firewall to enable ssh from known IP addresses only (here comes VPN into the game, if needed) and move SSH port to something else, but 22. You will be as safe as ldap and ssh and ssl are (exploits, exploits.. they're everywhere, you can't be 100% secure unless you disconnect the network cable from your server, remove the keyboard and USB ports)
So basically security is all about trusting. You HAVE to choose whom (and what) you trust.