Private tempstore storage contains data for previous anonymous user
Yes, this looks very much like a caching problem. You don't need to disable the anonymous page cache, though, this happens automatically for requests with a session cookie. What you need is a cache context session in render arrays containing session data, no matter whether you serve anonymous or authenticated users:
public function build() {
  $session = \Drupal::request()-&gt;getSession();
  $build = [
   '#markup' =&gt; $session-&gt;get('value'),
  ];
  $build['#cache']['contexts'][] = 'session';
  return $build;
}

The private tempstore is for large amounts of data. See What is the difference between \Drupal::request()-&gt;getSession() and \Drupal::service(&#39;user.private_tempstore&#39;)?