This is due to browser settings. Salesforce are aware of this issue, caused by the fact that Lightning and Classic (including Visualforce pages) URLs actually relate to different domains and that in LEX any Visualforce pages are embedded via iframes in the Lightning page. Most modern browsers now require "same site" cookie origin to allow cookies to be shared across the iframe boundary.
The "fix" can probably already be enabled on your org using the "Enhanced Domains" feature. As the documentation says:
This functionality is available on a rolling basis starting in the Spring ’21 release and is available to all customers by April 30, 2021
Consistent domain formats improve the user experience and reduce errors in code and API calls. Salesforce enhanced domains also comply with the latest browser requirements, allowing your users to access Salesforce using browsers that block third-party cookies.
When you deploy a My Domain with enhanced domains, all application URLs start with the org’s My Domain name and instance names are removed. Package names are removed from some URLs. The domain suffix (the part after the My Domain name) changes for Experience Cloud sites, Salesforce Sites, content files, Site.com Studio, Experience Builder, and Visualforce URLs. And Sandbox org URLs include the word sandbox, making them easy to identify.
And as per an App Exchange Tech Talk from last week:
Why? Comply with latest browser requirements to access Salesforce using browsers that block third-party cookies