Replay storage optimization through seed storing
Second, this is more of a technical thing than a gameplay suggestion, but it seems strange to me that you have issues with replay storage. I don't know how you store the game data, but the way I would do it is simply keep store of both teams that played and the initial seed for the match's RNG.
Even if this is a long, I imagine it wouldn't take an excessive amount of storage, and the match would always be reproduced faithfully since it's all deterministic. I don't know if you're actually keeping track of everything, but this seems like a more efficient solution if you are.