Solution:
sudo mysql -u root # I had to use "sudo" since it was a new installation 

mysql> ALTER USER 'root'@'localhost' IDENTIFIED WITH mysql_native_password BY 'new-password';
mysql> FLUSH PRIVILEGES; 
mysql> exit; 

sudo service mysql restart