I have this issue with youtube music only for some reason. For me "Shuffle" seems to be starting random, then after a handful of songs entering a loop of 6 or 7 songs. I never figured out why or looked it up, I just refresh the page. I know it must be only me somehow, but don't know what's happening.
I think you can have a rss feed of your playlist, you could grep the urls, | rand them like you want and play with mpv or just download everything with yt-dlp.
>I have this issue with youtube music only for some reason…
Try navigating to the playlist and look below the currently playing track. There should be a "shuffle type" button bar showing 'Familiar', 'Discover', 'Chill', etc. It seems to produce better results for me if I explicitly choose familiar tracks or discover mode (or the other options, but i use the first two 99% of the time).