Getting error "Your session has ended. Enter your password to log back in." every 30 seconds or so This is happening for all users and only on production environment. 

"Your session has ended. Enter your password to log back in."

Entering your password does not allow you to actually see the admin panel again.

Things we have tried:

Deleting the contents of craft/storage/runtime
Removing all rows from craft_sessions in db
Setting 'overridePhpSessionLocation' =&gt; false
Setting 'requireMatchingUserAgentForSession' =&gt; false
Setting 'userSessionDuration' =&gt; false
Setting craft/app/, craft/storage and craft/config as CHMOD 774
Changing craft/ folders to be owned by www-data
Setting session.auto_start = 0

Our environment is PHP 7 with Ubuntu 16.04 running Apache 2.4.18

Something to consider is we run with an Akamai CDN cache that is set to ignore our entire /admin directory, but my suspicion is that something elsewhere is getting cached. Thoughts about that? Is there another directory we should be ignoring?

Also as a point of info, our /craft folder is above the docroot so not publicly accessible and therefore unlikely to be cached.

Finally, what's very strange is if I remove the modal containing the error message from the DOM in Chrome Inspect, I am able to still navigate the panel fine, without having to re-authenticate. Error also happens in both Chrome and Firefox.
Thanks for the troubleshooting help. It appears as though the issue was the cache and how Craft handles sessions.

For those who use a cache/CDN and are having issues with control panel session timeout:

Even after ignoring /admin on our cache, the cached pages on the public-facing portion of the site were conflicting somehow with how Craft was handling the sessions in the admin panel.

Our solution was to create a cookie we called isAuth that was created on login and destroyed on logout. We did this by creating a plugin and using userSession.onLogin and userSession.onLogout.

Then we set our Akamai cache to no-cache, no-store if isAuth cookie is present. This fixed all timeout issues.