How The Magic Happens
You can observe quite a bit of this by asking SSH to be verbose. For example:
$ ssh -v someserver date
If you are really interested in details, ask for very verbose narration:
$ ssh -vv someserver date
Here's an overview of what you're going to see:
Your client host and the remote server authenticate to each
other using public-key cryptography.
Each host is certain that it has the other's public key,
since the administrator stored all those in
Host #1 picks a random number and
sends it to host #2 as a challenge.
The host #2 encrypts that challenge with its private key
to create the response, and sends it back to host #1.
Host #1 decrypts the response using the public key of
host #2 (which host #1 is certain that it has).
If the result is identical to the challenge, then that
must really be host #2 over there!
2 — The client and server negotiate a cipher and a session key. The cipher will be the strongest encryption algorithm that both hosts know. The session key will be generated with the Diffie-Hellman algorithm — see my "Just enough cryptography" page for details.
User authentication happens.
Now that the two hosts are certain of each other's identity,
and they have negotiated a secure communication channel,
the user can be authenticated.
Cryptographic challenge-response authentication is tried first,
as described above for hosts.
Since we disabled password authentication on the server,
that method has to work.
If the user forgot to run
they get mysterious remote authentication failures.
train your users to always run
ssh-add, or else
put something in a startup file to force them to do this.