Why does it take tens of seconds to get a shell prompt?

Quite a few things could be happening here. You can find most of the answers in your shell's manual, but those are usually incredibly long and oblique, so...

Chances are your problem boils down to one of a few things.

If your profile or bashrc have expensive things, consider trimming them back.

If your profile or bashrc use a reverse DNS lookup (to set the prompt or something), fix DNS or use hostname instead.

Shells open a lot of files, among other things, while initialising. If system load is high, it will often show up here.

If the banner is pre-authentication, it might also actually be authentication (pam, LDAP, etc.) that is slow.

It might be none of these things, though. A surprising amount of stuff happens right before displaying the prompt!

It's probably either waiting for DNS or trying to authenticate via LDAP or such.

Try to add UseDNS no to /etc/ssh/sshd_config

If it also does it on local logons, check if any LDAP servers or DNS servers you have configured are slow or unresponsive.

One possibility (covered by other answers) is that the process of setting up the SSH session itself is where the time is lost.

Another alternative is that your shell startup scripts running on the remote machine after SSH session establishment have something that is taking a long time (perhaps attempting to access some broken network mount). You can debug this second possibility as follows:

Temporarily add the following to the top of your ~/.bash_profile:

set -x
PS4='+ $(date "+%s.%N")\011 '

The set -x turns on some debugging for every shell command executed. The PS4 variable controls how that debugging is presented - specifically in this case we use date to add timestamps.

You may then analyze the timestamps of the debugging output to see which commands in your startup scripts are taking too long.

If it's an Ubuntu server, the default login setup checks if any packages are updatable every time a login shell runs. If the package lists aren't in disk cache, this can take a second or two even on a fast idle desktop.

$ ssh localhost 
Welcome to Ubuntu 15.04 (GNU/Linux 3.19.0-26-generic x86_64)

 * Documentation:  https://help.ubuntu.com/

*** System restart required ***
Last login: Sat Sep 12 01:38:38 2015 from localhost

To generate that "restart required" message, it had to check that the currently running kernel is not the default kernel currently installed. (i.e. there was a kernel and I didn't reboot yet.) It will also print a count of security updates available, if there are any.

I think this is the major slowdown in logging in to Ubuntu that's been introduced recently.

If not that, then your ~/.bash_profile / ~/.bashrc might be the problem.

Have you tried logging in to the server from itself (ssh localhost)? Or logging in a 2nd time right away? (To see if it's a lot faster when stuff is cached.)