Would "na" always come on the beginning of the phrase?
Well, na is a preposition, in this case, it's connected to to. So either Na to nečekáme. or Nečekáme na to.
Could I also translate it as "We do not wait for it"?
She clearly say mucekame
not for me