Usuário mchid respondeu a um pergunta semelhante declarando que:
apt só pode manipular 40 chaves em /etc/apt/trusted.gpg.d. 41 chaves e você receberá o erro GPG "sem chave pública encontrada" mesmo se você for através de todos os passos para adicionar a (s) chave (s) em falta.
Verifique se há alguma chave não usada neste arquivo de ppa (s) que você não use mais. Se todos estiverem em uso, considere remover alguns ppa (s) com os arquivos de chaves correspondentes em /etc/apt/trusted.gpg.d
Então eu fui para sudo nautilus /etc/apt/trusted.gpg.d
e deletei 2 chaves GPG (agora com 39 sobrando em /etc/apt/trusted.gpg.d). sudo apt-get update
funcionou OK e agora posso atualizar qualquer pacote.