Problemas con Github

Buenas a tod@s:

He modificado el nombre de usuario de mi cuenta de Github ya que tenía un nombre así en plan provisional, pero ahora que le voy a dar más uso pues me he querido cambiar de nombre y ponerlo uno más profesional.

El caso es que ahora me da problemas a la hora de logearme para subir código mediante la terminal.
He intentado logearme por SSH y hasta con Tokens, sin embargo el token lo tengo que renovar cada vez que tengo que subir código al repositorio. Y no me gusta.

Como puedo solucionar de forma permanente este problema? He mirado por internet y he visto lo del SSH pero lo del SSH no me termina de ir bien porque me devuelve el siguiente error:

Permission denied (publickey).
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

Y si lo hago con el usuario y el password me devuelve este mensaje de error:

remote: Invalid username or password.
fatal: Authentication failed for 'https://github.com/*******/*****'

Llevo un par de días buscando por internet y preguntando a compañeros y aún no hemos encontrado la solución. Hasta me he puesto en contacto con Github a ver si saben que puede ser.

Muchas gracias de antemano