Hi,
'And away we go' was a catch-phrase made popular by the American comedian, Jackie Gleason.
If you use the normal word order, it becomes 'And we go away'. ie we are commencing a journey. Your other suggestion would be 'And we go a way' which clearly (well, at least to me!) has less meaning.
Best wishes, Clive