Apologies if this is not the right forum to ask.

Yeah, it's the right place to ask.

Currently I have a setup which triangulates the surface and writes it to an STL file.

What is the input data of your triangulation algorithm? A point cloud or a mathematical description of a surface?

However, some of my meshes are complex, and the conversion from STL to a 'shape' in FreeCAD is unnaceptable slow.

A mesh is only a set of triangles without any information about the higher-level surfaces. Thus, converting a mesh to a shape doesn't make much sense in most cases because it only creates the BREP structure but cannot reverse engineer the actual surfaces.

So back to my initial question: if your input data is a point cloud you can first triangulate it and then use some algorithms to approximate the segments step by step. Here you need some robust algorithms for plane fit, cylinder fit, cone fit, sphere fit and a general NURBS fit.

If your input data is already a higher-level surface then you shouldn't triangulate it because this way you lose the information which you can't get back easily or even not at all. Instead you should try to create directly the BREP structure. The CAD kernel OpenCascade (OCC) that we use offers a wide range of standard (surface) geometries like plane, cylinder, sphere, ..., Bezier and NURBS surfaces. Now I don't know what kind of surfaces you produce but for arbitrary surfaces (some complex parametric surfaces or so) you probably won't find a counterpart in OCC. In this case you must describe or approximate it as a NURBS surface.