If you fire one companion, the person who joins should be able to re-hire them (at the King Crab, or in the hall of heroes if you have access to the homestead). At some point it should be possible to just transfer one companion over.