Academy of Illusion has the same wording. It occurs to me that it doesn't seem odd for Titan and Illusion because, outside of the card game, "a titan" and "an illusion" or "five titans" and "zero illusions" are nouns that can be quantified that way. You wouldn't say that someone experienced "a destruction" however. Destruction, by itself, is a noun that doesn't take quantifiers (like "a" or any numbers), making it unique to the other two mentioned. If it were "Destructor" or some other countable noun, then it wouldn't seem out of place. (No, I don't want it changed.)
Considering this, Titan's keyword (and Academy of Illusion) should just be left alone, regardless of what is done to clarify Academy of Destruction.
Update:
Bounty hunter refers to "a Legend card" in its text. Of course, in this case, "card" is not already established as the subject, so its being there makes perfect sense. It also doesn't have rarity as part of the adjective string.
Centaur trainer, on the other hand, mentions the next card being a rare Beast along with the established norm.
Golem Messenger uses Unliving as an adjective (no "a") without rarity after using the word card.
It seems to me that the apparent rule is that if "card" is already the subject, as in "next card" or "replaced card" or "targeted card", then saying the word card again is unnecessary. Use of "a" or "an" comes when rarity is mentioned (an uncommon Soldier, a non-rare Burning).
When rarity isn't mentioned, things become situational. Saying "will be a Beast" sounds better than "will be Beast", but "will be Undead" sounds better than "will be an Undead" since the word beast is a noun and undead is an adjective.