The Klingons took over 3 weeks to cross Federation space to Cardassian space in season 3 of DS9. Looking at any map of the Alpha Quadrant, the two empires have only a thinner stretch of Federation space between them.
It regularly took days or weeks for people to travel in DS9, to reach areas only halfway across the Federation so...100LY means they're travelling awfully slow for "maximum warp" or it's larger.
What about the Betreka Nebula Incident? It supposedly happened before the Fed-Klingon alliance, yet the Klingons and the Cardassians are on opposite sides of Federation space.
Where is the Betreka Nebula?