Is there such a thing as public key steganography

One of the draw backs of traditional steganography is that both parties need to exchange a secret key.

Don't infer from the implementation of one specific tool to the limits of steganography itself. Steganography is just the hiding of information within other data. It does not matter if the information you want to hide by itself are unencrypted, rot13, encrypted with a shared key or encrypted with PGP or similar. This means you can encrypt a message with whatever encryption system you like and then hide the encrypted message using steganography.

This is the first I've heard of keyed steganography, so I'll recap the article you linked, for the benefit of others who might be confused about it. They have narrowed down the number of steganographic algorithms they're analyzing quite a bit. The message must be embedded in a JPEG image (perhaps any raster image format?), and it can't utilize the entire image. The assumption they've made is that the person putting the message in has selected n pseudo-randomly selected bits, and the selection of these bits starts from a key of some kind.

They state that, given such an image, they can detect the bits that are part of the message. BUT, without the key, all you have is n bits, which has n! permutations (potential messages). You don't know their order, but if you find the key you can figure it out. Obviously, this mimics symmetric-key encryption. The key is kept secret, and the people who put the message in use the same key as the people who take it out.

The trick to getting an algorithm that uses a private/public key then would be to mimic the same algorithms in encryption. I don't have much experience with encryption algorithms, but finding a 'random walk' through some pixels looks an awful lot like elliptic curve cryptography, where the field is the pixels in the image. In fact, searching for 'elliptic curve steganography' yields results that looks promising. I haven't looked at any of them deeply though. At least the ACM hit looks promising.

Most of the steganography-based techniques are within the domain of private key encryption algorithms with the less security level rather than using public key algorithms. An attempt to create the secret code for image steganography for multimedia messaging service or MMS using elliptic curve cryptography has been demonstrated.

There's even a project on github. So it looks like the answer is "Yes, there is such a thing as public key steganography".

"One of the draw backs of traditional steganography is that both parties need to exchange a secret key."

No, steganography does not require any key (symmetric or asymmetric) as it doesn't use encryption at all. The real drawback of steganography it's that it is just security by obscurity; you hope the adversary won't discover the hidden message (or that you are actually communicating a message). Concerning this last point, often encryption and steganography are used together, to encrypt a message and then protecting the metadata.

EDIT: I wrote this before the OP edited the question. What is said above applies only to keyless steganography.