Good magical beast for a level 5 party

[Blu]

So, i'm gonna DM a game in some time and for the first quest the party will get is gonna be about hunting down a magical beast, i can work with different beasts but the encounter must involve hunting down an animal, to be honest even a dire animal or something like it could work.

The party consists of 4 characters, a human barbarian, an orc paladin, a kobold bard(with dragonfire inspiration) and an human warlock. I'm a little afraid the dragonfire inspiration might make the creature go down quickly so a tougher monster would be ideal.

So what would you recommend for a good CR 5~7 magical beast or animal encounter that can withstand a lot of punishment but still make for a great encounter?

[denthor]

Classic displacer beast about correct level three of them should do.

Rat king is a cr 5 creature entangled multiple giant rats. City sewer

Large hunting party of gnolls. With a ranger gnolls as leader. This would be a cat and mouse encounter they are out there hunt them down.

You want them to track the foe.

One single hill giant fleeing in the night memorable DC 10-15 to track. Pc may not be able to put it down but 4 ogres would do nicely if they should be burden and miss a fortitude save so they are fatigued.

[ImperatorV]

Hydras are magical beasts and can fall into the CR 4-7 range. They can be pretty tough due to the big fast healing values, although the easy source of fire on attacks will make it easier to sever heads if they want to do that. If you want to be nasty, a five-headed pyrohydra is CR6 and immune to fire. That's if the bard is using baseline dragonfire inspiration and not sonic damage or something equally silly.

EDIT: Depending on how optimized your party is they might be able to get the 5-headed hydra down too quickly though - even with the fast healing if they can put out a combined 40+ damage per round they'll kill it in two rounds. If this is the case just go for a bigger pyrohydra.