I haven't fought many of these, but they could increase in popularity with 2.3.2. This could be a much harder fight than I'm making it, but I've never really fought one that was hard (possibly due to player skill). Pretty much, Frost Mages are a counter to SP+Rogue, but this fight didn't seem too tough.

You should easily get a sap on the Mage, but don't if you think the Priest is simply going to run away on his mount. A Priest running away on his mount is the worst thing that can happen for you in arena. If you have to, just shiv the priest out of stealth. Remember, Priests have a high stun resist chance. The chance of a Priest resisting my CS is too high for me to open with it.Pretty much you just rush the Priest down while avoiding CC from the Mage. You'll want to pop a preemptive CoS if you need to. Remember to watch what the Mage is doing. You have 1 trinket to break sheep. Don't rely on your Priest to dispel you, or your target can get away. You can simply Sap->Silence->Fear->Blind the Mage, to lay down some pretty good CC on him. Unfortunately, he can break all of it but Silence, so it's merely an inconvenience for him. You should be able to down the Priest, but your Priest might need to pop out to heal a bit before your target dies. It's okay though, because you can solo a shadow priest in your sleep. Just make sure your Priest doesn't die. That would be a bad thing. The 3rd time we fought this set up, my Priest died just before theirs, and I had to 1v1 a Frost Mage with 0 cds and no prep. It's not pleasant, so avoid it.