I’m not sure there is a “fix” for this because it’s set by Apple in the algorithm they use for “Random”, but you might find some ideas reading through these forum discussions.
https://www.reddit.com/r/AppleMusic/comments/8lxndw/apple_music_shuffle_isnt_truly_random/
https://forums.macrumors.com/threads/why-iphone-shuffle-always-play-the-same-song.409372/
Some appear to be trying to increasing the number of songs with in a Playlist (giving a bigger pool from which to select so to speak), others suspect it has something to do with the algorithm giving priority to songs with high play counts, so resetting them all might level the playing field.
But realistically the only fix will be when/if Apple decides to employ a true Smart Shuffle function (that’s just my view).