How to efficiently shade a flat shaded mesh, smoothly.

Hello! I have just spent the past day implementing marching cubes algorithm and now have a result that looks like this:

And I have a shader that interpolates between a green and brown colour based on the normal of the current pixel. However, as you notice, it is very low poly. I ## have ## implemented interpolation to the marching cubes and it works. However, the shading is too flat. I have tried several things like averaging the normals, and sharing vertices, however, this just has a ugly result and is very slow. How could I get a result like this:

https://imgur.com/a/HtOefvd