"обычно" suggest that it is what you usually do in general, so you need to use the present tense. "с женой" should be at the end according to the Russian word order rules.

Никогда. Обычно мы путешествовали ( или «путешествуем» - настоящее время) с женой

❤️❤️