How about the Federation Starship Destroyer a vesel created by all of the federation allies including the Klingons to battle the Borg set after the return of Voyager.
Could have a contingent of Klingon warriors on board to defend against infiltration.
Just a thought?