Because "dog" and "cat" are direct objects of the verb so they have to be in the accusative case. And the accusative of masculine animate nouns is formed by adding -a at the end (and removing -ie- in the case of "pies")
It seems that the accusative form of most masculine animate nouns is the same as the genitive, including in the adjective. Mam małego psa, for example.
They're Instrumental, they wouldn't be used for "We have a dog/cat", they'd be used for "Odie jest psem, Garfield jest kotem" (Odie is a dog, Garfield is a cat).