Use Kerberos instead of Rshell/Rlogin/Telnet
Kerberos keeps plain-text passwords from going over the network
Kerberos is
free
easy to set up
works well in a LAN environment
offers the functionality of rlogin/rshell/telnet without the security exposure