One way to avoid this is to ensure all data exchanged is encrypted. This is what SSH - Secure SHell - does: the initial connection between two system allows for the transfer of information, including public keys. A session ID is calculated by both parties. That session ID is then used as part of every piece of information exchanged, to ensure the connection is encrypted, and thus considered much more secure.
ssh is quickly becomming the prefered method for connecting to remote systems.
ssh is first introduced (because it is considered secure), even though it is still not found on all UNIX/Linux installations. telnet, on the other hand, is found on all UNIX/Linux platforms, as well as on the MS Windows 95/98/2000/NT systems.