Para quem ainda estiver com problemas ao conectar ao banco mesmo usando o comando
ALTER USER 'root'@'localhost' IDENTIFIED WITH mysql_native_password BY 'novasenha';
Tente o mesmo, mas sem "@'localhost'":
ALTER USER 'root' IDENTIFIED WITH mysql_native_password BY 'novasenha';
Pra mim resolveu apenas depois de remover o @localhost. Estou rodando em um container Docker e acredito que possa estar relacionado a isso.