A senha de um usuário pode ser excluída com:
passwd -d <user>
(como root / com sudo).
A autenticação baseada em chave SSH ainda funcionará, mas não será necessária uma senha para definir uma nova. Eu testei isso no Ubuntu agora.
tom@slappy:~▶ ssh foo@shell
Welcome to Ubuntu 11.04 (GNU/Linux 2.6.35.4-rscloud x86_64)
* Documentation: https://help.ubuntu.com/
Last login: Sun Jan 15 12:10:44 2012 from 12deee6f.bb.sky.com
foo@shell:~$ passwd
Enter new UNIX password:
Retype new UNIX password:
passwd: password updated successfully
foo@shell:~$
Quanto à segurança: não vejo por que isso deveria ser um problema. Qualquer pessoa que tenha a chave privada será capaz de se conectar e fazer mal, independentemente de uma senha ser definida ou não. Conhecer a senha depois de conectá-la pode fazer com que ela cause mais danos se a configuração do seu sudoer estiver um pouco deficiente, mas isso indica que você tem maiores problemas de segurança, na minha opinião.