The Random Battleground option can be found in the Battleground tab of the PvP frame and is only available for level 80 characters at this time. https://wowwiki-archive.fandom.com/wiki/Patch_3.3.3
Try again. It was never available to lvl 70s, and blizzard themselves said it’s only being hidden from level 70s, not removed from the game.