ubuntuにmysql5.7をインストール後rootのパスワードを変更してもログインできません。。。

os ubuntu 18.04
mysql 5.7.31
サクラVPS使用

現在Ubuntu18.04にmysql5.7.31をインストールしてrootユーザーのパスワードを変更する作業をしている中、変更しても

Access denied for user 'root'@'localhost'

となってしまいログインできません。
唯一ログインできるのは

sudo mysql

とした場合だけで、これではLaravelとmysqlを繋げないなと悩んでいます。

やったこと

セーフモード使用でrootのパスワードを変更　-> ログインできず

$sudo service mysql stop
$sudo service mysql start --skipgrant-tables
$mysql -u root

'エラー'
Access denied for user 'root'@'localhost'

$sudo mysql
mysql>mysql_secure_installation
設定略
$mysql -u root -p
'新しいパスワード入力 '

'エラー'
Access denied for user 'root'@'localhost'

$sudo mysql -u root -p
'パスワード入力'
mysql> 'ログインできました'
mysql> ALTER USER 'root'@'localhost' IDENTIFIED WITH mysql_native_password BY 'パスワード';
mysql> FLUSH PRIVILEGES;
mysql> exit
$mysql -u root -p
'パスワード入力'

'エラー'
Access denied for user 'root'@'localhost'

sudoをつけないとダメな様で,初心者の私には解決の糸口が見えておりません。
まずsudoを外して、アクセスできないとlaravelに繋げ無いものだと思っていますが,どうでしょうか？
方法を教えていただけると嬉しいです。
先輩方、どうぞよろしくお願いいたします。