If i remember correctly, i've experienced this problem a while back. I think it was solved by delete 1-2 files in the Steam folder. Though i can not remember which files. But i'll have a look around and see if i can find the page that helped me.

BTW: Since you have access trough Wine, issuing a "De-Authorize All Other Devices" (Settings > Account > Manage Account Security) from there, then try logging in again from Linux MIGHT be worth a try. Note: This might require reactiivating the cellphone app on you cellphone as well though.

(perhaps it can even be done by using just the phone App, which would be easier. I've not checked app settings if it's even an option there though)

Another tip, which i'm also not sure will work or have tested myself:

Try running Steam in linux terminal with the -login <[username]| [password] argument (or simply just the steam command alone might even do). That miight give you some clues trough the terminal output as to what/where things are going wrong.


(Note: remember to clear bash command history etc. aftwerwards, regardkess if it does work or not, so that there's not ever any Steam password left stored as typed cleartext:

and/or
)

Feel free to contribute here:
https://github.com/ValveSoftware/steam-for-linux/issues

I seem to remember seeing a similar issue with login credentials being forgotten randomly. There are also other connection related issues there too.