What about instead of extra gyms we have ...something else? Something different. They can function like gyms, but are more unique in that they share a connection with the region's history and are made available post-game. This way we still keep tradition, but also have something new that isn't also the Battle Frontier. For instance:
Five castles, five knights. Each represent the five loyal followers of the region's first hero who was treated almost like a king way back when. You notice their castles while traveling the region, but they are always closed off for the main part of the game. However, we do run into these five leaders along our way as they assist us in stopping the region's evil organization from completing their ultimate goal. After all, their duty is to protect their region.
In the post-game, their castles or towers, whichever seems preferable, becomes unlocked and there's a small storyline that leads us to challenging the five of them. After we have defeated them, we go on to challenge the region's current royal king or queen, who only accepts challenges from those who have defeated his/her royal knights. This person could be a descendant from the region's first hero and the strongest trainer in the games.
It also works so not every type is used more than once: 8 Gyms (8 types)+ 4 Elites (4 types) + 5 Knights (5 types) = 17 types total. While the region champion has a variety of Pokémon as does that king or queen.
As the plot thickens, there's a secret that there was once a sixth knight and still is. It is hinted that the region's champion is one of them.
