They aren't marked on the maps. Probably because they are not Family Restrooms; they are Companion-Assisted Restrooms as Christamae reported and if they were on the maps people would be using them as Family Restrooms.
Although all the restrooms in the parks have "handicapped stalls", most of those are not large enough for someone who has to bring a wheelchair or an assistant into the stall with them. And (since they are inside restrooms, they don't work for a person with a different sex "helper".)
In MK and Epcot, these few companion restrooms are the only stalls in the whole park that can be used by someone who needs to bring in a wheelchair, an assistant or a have a safe bathroom when they are with an opposite sex caregiver.
I mention this because on our last trip to WDW, we often had to wait in quite a line behind people who apparently did have other options, but were using these restrooms as Family Restrooms. I'm not judging anyone's use of these restrooms (maybe they had some reason for using it that was not apparent to me). I'm only suggesting that people think of the options they might have and keep in mind that some people have no other options.
As the others mentioned, the companion restrooms are one room with a toilet and a sink - no stall. So, you would have no privacy whatsoever. If you use them, what you could do is have the girls stand right outside the door and keep talking to you or something so you know for sure they are still outside the door.
The restrooms in First Aid would be better, since there are CMs nearby. All of the First Aid stations actually have a waiting area with chairs, where they girls could wait for you. One thing to be aware of is that the restrooms in First Aid don't have locks on the door (so the CMs can get in there if someone becomes ill and needs help). It does tend to "hurry you up". They don't have an "Occupied" sign for the door and we have had the door opened when I was in the First Aid restroom with DD.