Initiative does indeed play a huge role already in normal battles. In arena where it by design should be made fair for a lvl 50 and 80 to fight solely on the effectiveness of their lineup does mess up the whole concept when it comes down to initiative.
However, with the way the game developed, initiative is already playing a vital role deep into the game, including passive barriers, etc. Finding a solution is one thing, possibility of implementing said solution is another. Of course, working your way around someone with higher initiatives is one of the charms of the game (personally), with talents like root of warrior and ninjas like sailor sakura and gakido allowing you to remove debuffs, or someone like Ao or shikamaru to control the ninja the round before to completely stop the mystery from being even casted. (That being said, fighting against an experienced player with proper knowledge of the game can put your lineup at a disadvantage still)
Having 2 fights with rotating initiatives would take quite abit of time, especially when 2 non-offensive builds fight. Furthermore, even with rotating initiatives, how does the system work after recording 1 win and 1 loss? (As this would seem to suggest) With ranked arena where win and losses do matter, having 1 win and 1 loss just leaves you stagnant at your rank. (Assuming losing and winning loses and gains the same amount of ranked points)
Just some thoughts after reading your post ^^