「どの公開鍵でなのかを伝えるために公開鍵を送る」とあるけど、
ただしくは「どの公開鍵でなのかを伝えるために秘密鍵を使う」です。

動作の詳細は自分もはっきり説明できるわけじゃないんだけど（SSHv1と
SSHv2でも少々異なるようだし）、たとえばユーザＡとしてログインしようとしてるとして、
まずSSHクライアントが「この秘密鍵ログインしたい」とサーバに伝える。
んで、SSHサーバ側で、その秘密鍵に対応する公開鍵が
/home/ユーザＡ/.ssh/authorized_keysに登録されているかどうか見る。
で、登録されているクライアント公開鍵でランダムデータを暗号化してクライアントに送る。
クライアント側ではその暗号化データをクライント秘密鍵で複合化して送り返す。
クライアント側の秘密鍵で正しく複合化できたら、クライアント側の
秘密鍵とサーバ側にある公開鍵が正しいペアだと証明できるので、認証される。

ってな具合だと思う。（本当はもっと複雑なことやってるらしいが）