You see dust as a problem but it’s easiest way to decelerate.
Why not to go big in order to increase redundancy? Make planet sized ship, accelerate it by halo drive, and lasers. Don’t decelerate, the expansion of The Universe plus matter of the intragslactic space will help you up. Just spawn smaller ships, which will resupply you and build lasers for your acceleration. So there is no such a problem as redundancy in hundreds millions years scale for earth like systems.
In the most radical case, you could reassemble your galaxy and push it by creating artificial quasar. And this will be fast.