In a Commander game can you choose a new commander if your original commander is stolen and then destroyed?

In Commander, your commander is designated before the game begins and is fixed for the entire game — you cannot choose a new or different commander mid-game under any circumstances. This is established in the Commander format rules, which are built on top of the Comprehensive Rules (CR 903.3, CR 903.4).

However, the important consolation is the Commander Replacement Effect (CR 903.9a): whenever your commander would move to any zone (graveyard, exile, hand, or library) from anywhere, you may choose to move it to the Command Zone instead. This applies even when an opponent controls your commander — the owner still makes this choice. So if an opponent steals your commander and then it gets destroyed, you can redirect it to your Command Zone rather than their graveyard.

This means that even in the worst-case scenario of your commander being stolen and destroyed, you are not permanently cut off from it. You can cast it again from the Command Zone on a future turn, paying the commander tax (an additional 2 colorless mana for each previous time it was cast from the Command Zone, per CR 903.8).

Concrete Example: Your commander is Atraxa. An opponent casts Gilded Drake and takes control of Atraxa. A third player then destroys Atraxa with Doom Blade. When Atraxa would go to the graveyard, you (as its owner) may instead place it in your Command Zone, ready to be recast for its mana cost plus the commander tax. You do NOT get to pick a new commander like Elesh Norn instead.

So the key takeaway: your commander identity is permanent, but the Commander replacement effect ensures you always have a path to get your original commander back into play.