Acho que você está procurando usar o foco errado. É desejável que todo e cada um desses funcionários tenha sua própria conta com sua própria senha e as contas sendo desativadas / destruídas quando saírem (você pode desativar o root neste ponto). Use algum sistema centralizado para gerenciar as contas de todos os clientes e defina os privilégios de cada usuário, com base em grupos ou usuários.
If it's the modification of the sudoers files on each host and disabling root passwords, how do you manage these sudoers files and keep everything up to date and consistent?
Use um gerenciamento centralizado de contas, como o LDAP.
If it's just using root keys, what can be done to protect/refresh these keys on a regular basis?
Se você seguir o acima, acho que isso não será mais necessário, certo?
how are others using tools to perform regular refreshes to ensure security?
Talvez você devesse começar a escrever uma política de segurança para seu ambiente específico. Existem vários conselhos que talvez não se apliquem ao seu ambiente específico. A autenticação centralizada pode causar mais dores de cabeça do que resolve, mas para mim parece a solução mais sensata.