Tente baixar o link (supondo que você esteja em um sistema x64) e instalando-o usando
sudo dpkg -i [filename]
Esta é a versão do libreadline6 disponível nos repositórios oficiais do Debian.
Quanto ao problema com a chave ruim, eu não acho que isso seja realmente um problema - apenas algo para estar ciente de que esse ppa em particular não está funcionando corretamente.