Use a distributed shell like mssh or dsh
Is it really a problem not being able to log in directly as root?
I always log in as a regular user and only use sudo to run administrative commands.
I accept it is a problem not having centralised control, especially when you need to perform a change on more than a small number of servers, but you can use something like mssh or dsh from your Linux Desktop machine to run the same commands on each server.
An example of the steps needed to connect to four servers and run a command as route would be
connect to all four servers using mssh, (eg mssh host1 host2 host3 host4 )
type your password if you don't have keys set up
run sudo "command"
type your password again
Surely you are permitted to set up keys for your own regular user account. Also you can set up aliases for groups of servers in mssh.
Then the steps become trivial
There is some more information on my use of mssh here