That should help for new cards.
If not, try, on the desktop (probably it works on AnkiDroid as well, if not it's something that should be fixed), to change that setting to "... new cards: .. order added" and back to "new cards ... random order". That's what i do.
There is also the recommended way, which is
even more complicated, i.e. involves more clicks.
(I thought i had reported it, but can't find the issue now. I think the order of newly added cards should automatically be randomized when added. They are, shown in order even with the random setting on. I think the reply was more or less "
working as designed".)
All this does not apply to cards you've already seen. Here the only thing i can think of is to use different reply buttons to break the order.