Traditionally the petrifying power of a basilisk (and cockatrice, and gorgon) lies in its gaze. Doesn't necessarily need to be reciprocal (the victim doesn't have to meet the gaze with their own). So if some of the party can hide from sight or attack from behind they can avoid the effect a bit longer.
But in general any creature with petrifying vision is going to be quite dangerous in the hands of a smart GM. I put a single pampered basilisk and its two skeleton attendants on one of the higher (and thus harder) floors of the
Deathspine in part because it's such an effective threat. Even moreso if it has sidekicks to do the actual killing while it handles paralysis duties.