I am running a Skulls and Shackles campaign with 5 PCs. They are currently on the second book and they are completely pushing through each encounter as if there is no threat whatsoever.
My PCs are all level 4. Samurai, Druid, Cleric, Summoner, and Sorcerer.
The books I've allowed are all the Paizo released ones: Core, Advanced, Ultimate.
I realised they are just blowing through these was when they attacked their first ship to steal it. The book called for putting one CR 3 Marine and one CR 4 Officer. I thought it was going to be too easy to have 5 on 2 so I added 4 more Marines. They sliced through these guys without taking so much as 1 hit.
I am not a fan of increasing HP and AC to prolong the battles so I am trying to think of another way to give them somewhat of a challenge.
Any advice for me?
Skull and Shackles is overall a rather easy adventure. The 4th book can have some tough encounters but my players also did mostly everything easily.
My best advice is to let them shine on the not so relevant encounters and redesign the tougher ones by adding more minions and giving the baddies better feats/spell selection, etc.
On the second book our swashbuckler ended the final boss on a single turn before he could take any actions. Isabella was tougher.
Skull and Shackles came out before Advanced Class Guide and Unchained. Consider rebuilding NPC Fighter/Rogues as Slayers and give those dex rogues dex to damage.
With 5 players you are over the 4 players assumption of the AP. Consider giving enemies perks to action economy. More enemies, adding healers and casters to some fights.
Give enemy ships tactics. Throw fishing nets on casters, get archers in the rigging, ships are full of choke points, cover, caches of healing potions, use boarding pikes, etc. Use the ship; swing rigging at them, pull cargo grating out from under them if the are standing on it.
Use the "background combatants" that are assumed to be fighting your crew off camera. Extra mooks enter the fray, you catch sight of a beloved NPC in danger nearby.
Part of the fun for our group was the personality of the crew. This won't make fights harder or easier per se but as leaders of a crew they knew who was really loyal, verses in it for the money, there were cowards on the crew people with baggage and so on.
Try to figure if your group is hard to hit by enemies you can drop advanced template more often this will raise enemies AC. If the issue is action economy drop additional enemies.