As I posted previously:
"And if that small insect has the ability to replicate, or if more of them are available in the first place, you can imagine your problem solved."
If we get into details, it can only get speculative.
Back on track: there's absolutely no reason the ship needs to be large. Being small is much more practical, being cheaper and having redundancy by being able to send large numbers of ships.
But there's the added and not necessarily related fact that the ship can be fully automated and doesn't need humans inside.
And this by itself partially solves the fuel problem, as the trip can take far longer and thus be cheaper.