Ah, use o programa passwd como raiz :
sudo passwd root
Ou, se você já está executando como root (o que você não deveria), apenas:
passwd
O argumento root pode ser omitido, porque quando você executa passwd , o padrão é o usuário atual (que é root, pois somente root pode alterar a senha do root).