I was having the same issue, but not on every users. Only my personal user was apparently impacted. I am using Nextcloud’s native authentication, no LDAP or OAuth integration.
Check if you are running in the same issue, run the following query:
SELECT uid, count(id) AS nbtokens FROM authtoken GROUP BY uid;
If a user has a high number in column nbtokens (> 100), login can take more time.
In my case I don’t bothered about reconnected some devices, I just deleted every tokens I had in this table.
DELETE FROM authtoken WHERE uid = 'myuser';
Don’t forget to replace “myuser” by your actual username;