Por que você usa sudo ssh
para se conectar? Você pode usar o cliente ssh no modo de usuário!
Para instalar o servidor ssh em uma caixa do Ubuntu, execute
sudo apt-get install openssh-server
Em seguida, o ssh para essa caixa deve funcionar. O Telnet não deve ser usado pela Internet devido à falta de criptografia.