How to smooth edges on a keyed object

Hello everyone,

I currently have a project where I have to key out a multi-colored logo-background that someone set for the recording by mistake. As you can see on the left in the picture below, the edges are already not perfect in the original, and after I keyed out the colors with the Color Key effect, the edges are even sharper. I would like to soften them but don't know how. The Edge Feather effect seems to only work on the actual edges of the original image. The video is quite long so masking every frame is not an option. 

If anyone has an idea how I can improve the edges, please let me know!

Thanks!

Greetings

original // keyed out