This is a problem I have seen a few times, and is usually when using apache.
If there are any stray characters or new lines before the opening <?php in any of the files that get executed then those characters are emitted by the web server before cookies are prepared and sent.
This blocks cookies from being send to the client, and the client has to start a new session on every request.
Unfortunately, the only solution is to look at every file you have created or modified (not too bad if you use Git) and ensure that <?php are the first characters in every php file.
You can ignore view files because they are not used until after the cookies are sent.
Most likely candidates are controllers, service providers and route files.