Do Germans really associate that phrase mostly with Hitler? I find it quite surprising because despite not being German (nor German-speaking) I know that this phrase comes from the first verse of the Deutschlandlied.
The verse of the Deutschlandlied that contains it is also no longer used, only the third verse is the national hymn.