Oh, I see, you original sentence was "МY dog аnd i went for a walk with you". I did not notice "with you" part.

In this case, I would prefer "Мы с тобой пошли гулять с моей собакой". It sounds more natural. I combined the humans to "мы с тобой" construction, and I moved the animal separately. Since "гулять с собакой" is a kind of activity where "с собакой" more relates to "гулять" (clarification of the verb) rather than to the participants.