Mage is one of the more interesting classes in duels because of it's unique consistent 'blandness'.   The class does consistently well, but has few 'highroll' treasure combinations and 'lowrolls' as well. Your starting treasures are all mediocre, with your choice for what to start not being as impactful to your run as it would be for any other class.

Starting Passives: Mage possibly has the largest amount of good starting treasures including: Rhonin's, rush, recycling, caltrops, robe of the apprentice, plaguebringer.

Second passives: Second passives can get a little more difficult to get good ones, but still like the starting passives there's a good chance to get a good one, yet little chance you get a 'guaranteed 12 wins' like hunter would with double deathrattles. Good treasures would include: Disks of legend (my last 12 win mage run included only ras, jandice, and ivory from starting deck but it still worked wonders.), Double Time, From the Swamp, Caltrops, Khadgar's orb, Emerald goggles.

The deck does extremely well at simply outlasting opponent's and finishing them off with a Ras combo, a huge Grand Finale, or even Keywarden Ivory bringing high value. Not to mention just how much your hero power tokens can shut down large minions and attacking classes.

Replacement card: 

Brain Freeze is the best card to replace anything (could be argued that it is already better than Arcane Explosion)

Edit: The ice shard hero power got nerfed into oblivion, don't use this build. Will likely make a new build soon, but for now just know that you should be using the wyrmblast hero power.