As someone with a serious soy allergy, I am not a fan of this either.
in the context of this sentence, neither 'change' nor 'switch' are quite right.
as mentioned in the posts already; 'replace', 'exchange' or 'swap' would provide a more natural english translation. also, as hippietrail has noted, in english 'for' needs to be an accepted preposition, depending on the verb:
'they replaced my egg/s with tofu'
'they exchanged my egg/s for tofu'
'they swapped my egg/s for tofu'