I may be wrong, but it sounds like you have a sessions issue. You can try running the following in your SQL Database to see how many sessions it has
SELECT COUNT(session_id) AS Sessions from ost_sessions;
If its a very large number, than that could be the issue and old sessions aren't clearing out. I had an issue a few years back where it wasn't clearing out and users would log in, then have to login again on every tab they selected. I can't quite remember how it was exactly solved, but I know it had something to do with enabling Auto-Cron and there was a clean up function. I know there's something here on the forums about it as thats how I found the solution.
Granted this may be different as most of my Agents very rarely log in as a user.