Se você está pedindo o cliente telnet, ele já deve estar instalado. Tente digitar telnet
em um terminal. Se não, sudo apt install telnet
irá instalá-lo.
Você não quer servidor telnet. Não há motivos para usar o telnet em 2018. Não é seguro e não oferece benefícios.
Para configurar o SSH, simplesmente
sudo apt install openssh-server
sudo systemctl enable sshd
sudo systemctl start sshd
Se você tem firewall configurado, você pode permitir ssh com sudo ufw allow ssh
.
Para configurar o login baseado em chave, this Q & A pode ajudar.