Resolvido. A coisa que não levei em conta é que o script é executado como root e não com meu usuário. Portanto, ao executar ssh, a senha é necessária, pois eu apenas configuro as chaves para o meu usuário. A solução que usei é forçar o ssh a usar minhas chaves de usuário:
ssh -i /home/user/.ssh/id_rsa user@remote sudo halt