I don’t know if it’s a bug or just bad luck. Using the same deck I used the “random order” option several times on several profiles. It seems to me that the “random order” is very little random it works more like it uses a pattern.
Does this post explain your issue? Showing new cards in random order