This seems like an English construct translated directly into Irish. In Irish one would say "We brought the new dog home with us".
Thugamar an madra nua abhaile linn.
I think your suggestion is more natural in English, too, not just in Irish.
Since "tóg" can mean "build" or "take," and "thógamar" can mean "we built" or "we took," shouldn't it be correct to translate this sentence as "we built the dog a new home?"
No, because the adjective nua is qualifying the noun madra it means "new dog".
The English sentence "we built the dog a new home" is a bit tricky, because "the dog" isn't the object of the sentence, "a new home" is the object, and the Irish would be:
Thógamar baile nua don mhadra
I think in many cases Rinneamar teach nua don mhadra would be preferred, because it avoids any ambiguity in tóg, as a dog's house is often portable, and teach would be preferred even for a home for a person. While abhaile and sa bhaile are translated as "homewards" and "at home", baile on it's own is more likely to be interpreted as "town".
Thanks! I very much appreciate your thoughtful response! As you'll see from below, I didn't fully read the whole sentence — not really grasping the word order, OR the use of abhaile vs. teach! DOH! (BTW, your suggestion of using rinneamar to avoid the ambiguity of tóg is great!, too)