MArcomage

Skeleton warriors has same cost & rarity, but does hals Dmg.

The drawback is that Rogue pyromancer may replace one of your good cards with a Searing fire, which isn't that great.

It just might replace a non-burning non-usefull card by a burning one (being Searing fire) wich is usefull in burning decks, + it has an extra keyword.

Right. It's a good card to put in burning decks, but it could still replace a good burning card (like Nightmare) with Searing fire. Hence the "rogue" adjective. That's why I think 15 damage for the price is a good trade off.

Even with the randomly selected trade-off, it's still too powerful for a Common with so low of cost. If you start a match with three of these on hand, not an impossibility for any common, you could decimate your opponent in three easy turns. (Literally, as "decimate" means to reduce to one-tenth. 50 -> 5. Never mind.)

My suggestions would be to decrease its efficacy (10 attack would bring it in line with the cards that deal damage only if a certain resource is higher than your opponent's), give an additional resource penalty based on the rarity of the discarded card, choose higher rarity or higher cost or keyword cards first, or have it create more than one Searing fire, possibly a random number from 1 to 3.

I like the most recent change, 5 attack + bonus for rarity. May need some tooling for the bonus numbers, but it now stands as a much more interesting (and delightfully unpredictable) card.

How should it target the card for discard? Completely random, or it should pick some rarity group first - for example it should seek rares first, uncommons second and commons last or vice-versa?

I think it should be random. That's why it gets a large bonus for targeting rares. Plus, it's not really card cycling because you're basically burning your deck to do more damage.