I grinded priest to legend a few days ago so I naturally played this matchup a lot. Without knowing your exact deck list it's pretty hard to comment so I'll post mine that I adjusted a bit for the paladin/patron heavy meta I faced.
One thing I learned was that keeping deathlord is actually not advisable in the list I ran, despite being a very strong anti aggro card obviously. As crazy as it sounds, you cannot afford to skip your first 2 turns against such an aggressive deck without falling pretty far behind. you need to hard mulligan for your 1 drops/pyro (with coin, don't play it on turn 2 though!) and if you run the list I do, with 8 playable 1-2 mana minions you're very likely to get one.
some general tips for the matchup
when you're on 3 mana and they played muster for battle, going for example pyro, coin, heal pyro is a totally fine play if it clears their board. I try to avoid lightbombing just the challenger usually even if it means taking quite a bit of dmg the following turn (depending on my life total of course). I find harrison to help a lot because it allows you to entomb the challenger and save the light bomb for boom/big board because you'll have a way of dealing with the ashbringer.
Prioritize drawing whenever possible without totally giving up board control. You have all the answers you need, you just need to get them into your hand. most of the games you beat secret paladin easily in start with turn 1 chow or cleric.
I wouldn't worry too much about divine favour (some ppl might disagree with this).
Your cards are on average more valuable than his and priest often times relies on combos. I think keeping circle is fine when you already have a cleric for this reason. It allows you to both cycle and keep your board intact.