Telnet login prompt is slow

[mwtown@mmm.com]

Ok, I'm pretty much a newbie to the sysadmin side of Linux, and since I
wasn't able to make it to the InstallFest (for which I am bummed), I'll
post my question here.

I have a Linux box set up on my home network, which I will be using for (at
the very least) a file server for the whole network.  It has an AMD K5-133,
128Mb, 2.1Gb HD (more to be added when I have it working to my specs), a
3C509B-TP NIC, and I have RedHat 6.0 installed.  My problem at the moment
is the face that whenever I try to telnet into the box from my windoze
machine, it takes a good 1.5 - 2 minutes for a login prompt to come up (It
connects right away though).  I'm at a loss as to why this is happening.

This morning, I've just learned that my friend's server (which runs on his
DSL line) started doing the same thing when his DSL line went down on
Saturday morning.  He's running SuSE (one of the newer versions), so that
rules out the distro package.

The only thing I can think of now is that it might be that I don't use a
DNS (since the Linux box is on an internal net) and he can't access one
while the DSL line is down.  Am I thinking correctly on this?  How do I
check?  If it is, how should I go about fixing it?

Any help is appreciated  :)
Mike Town
mwtown@mmm.com