Tenha em mente que o servidor tem uma chave pública e privada que é completamente separada do par de chaves que você gera como usuário. A chave privada do servidor geralmente é armazenada com a configuração do servidor e a chave pública é transmitida pelo servidor quando você tenta se conectar. Você cliente compara a chave pública do servidor com o seu arquivo known_hosts. Se usado corretamente, isso evita ataques MITM.
Você tem a chave privada da sua conta pessoal. O servidor precisa da sua chave pública para poder verificar se sua chave privada da conta que você está tentando usar está autorizada.
Então, use o seu exemplo. Bob e Alice têm chaves privadas e chaves públicas. As chaves públicas que foram compartilhadas antes ou como parte da conexão são usadas para verificar se os dados criptografados pelas chaves privadas são legítimos. Se o cliente não tiver a chave pública ou tiver uma chave pública diferente, você receberá um aviso assustador. Se o servidor não tiver a chave pública do cliente, você não poderá entrar.