When navigating site, user becomes logged out?

This one is a bit frustrating. On my site, user logs in fine, but then seems to be randomly logged out when navigating the site. The membership sign in widget reappears on the side bar and the WP top bar disappears. I am able to log in again as same or different user.

I'm not sure if this is a cache thing? However, I can't expect the user to empty cache every time they use the site.

Any thoughts?