All my companions are dead. :( Should I just start the game over?

I doubt it. You don't need them to solve the game.
They're pretty much doomed anyway. They don't level up and you can't improve their armor. Once you're facing tough opponents with big guns, the NPCs can't take more than one hit without being torn to shreds
Early in the game, Ian is great to have along because he's a huge help in the battles. Once you get to around 8th or 9th level and have tricked yourself out with all the fancy armor and guns, your companions don't really have much impact on the battles.
It's possible to keep them alive through the end, but you only get style points. You actually have to go to a lof of trouble to do this. You must solve the last two quests in a specific way and go out of your way to protect the NPCs from getting shot at and keep healing them up.
I know it can be done, because I managed it. But unless you're really lonely, I wouldn't bother to start over. Just shed a tear for Dogmeat, and move on.

It mostly depends on how far you're into the game. In the beginning Ian was a great help for me and when I got Tycho they were still useful, as they dealt at least some more damage to the enemies. It also wasn't a lot of trouble, as long as I kept the enemies focused on me. Only occasionally I had to reload a fight so that my companions didn't just go get themselves killed. And if any situation was too tough for them I could still leave them and pick them up again later.
But, actually, once I got good enough armor and weapons I really only kept my companions for the "style" as mcfeher said, I wasn't dependend on them anymore at all. So, if you're already able to hold up on your own I agree that you shouldn't bother. Going alone might then just spare you some trouble, as the companions (unfortuantely) don't influence the story at all, anyway.

They sure make great mules, though.