How to find connected mesh triangles?

No, there's no way around analysing the actual triangles. However you can store the neighbor information in a dictionary. To do this you probably want to first create a dictionary with all edges. That way you can simply iterate through all triangles and first store which edge is shared by which two triangles. Once you have that you can simply look up each of the 3 edges for each triangle to determine the 3 neighbor triangles. So at the end you have a dictionary which gives you a list of 3 triangle indices for each triangle which will be the neighbors of each triangle.

Keep in mind that finding shared edges of triangles which do not share the same vertices is a bit more tricky. So it depends on what kind of mesh you have and if the vertices are actually shared between the neighbors. If you have a fully shared mesh you don't need to access the vertices at all since all you need are the indices of the triangles. However if your mesh might have "seams" (different UVs, normals, colors, ....) you have to manually match the different vertices based on their positions. In this case it gets a bit tricky since identifying the same edges is more complicated. In this case you may need another step to create a vertices lookup to determine which vertices are actually the same.

I just had some time and quickly wrote this helper class:

 public class MeshTriangleNeighbors
 {
     public class Vertex
     {
         public Vector3 position;
     }
 
     public struct Edge
     {
         public Vertex v1;
         public Vertex v2;
         public Edge(Vertex aV1, Vertex aV2)
         {
             // ensure the same order to guarantee equality
             if (aV1.GetHashCode() > aV2.GetHashCode())
             {
                 v1 = aV1; v2 = aV2;
             }
             else
             {
                 v1 = aV2; v2 = aV1;
             }
         }
     }
     public class TrianglePair
     {
         public int t1 = -1;
         public int t2 = -1;
         public bool Add(int aTriangleIndex)
         {
             if (t1 == -1)
                 t1 = aTriangleIndex;
             else if (t2 == -1)
                 t2 = aTriangleIndex;
             else
                 return false;
             return true;
         }
 
     }
     public class Neighbors
     {
         public int t1 = -1;
         public int t2 = -1;
         public int t3 = -1;
     }
 
 
 
     Dictionary<int, Vertex> verticesLookup = new Dictionary<int, Vertex>();
     Dictionary<Edge, TrianglePair> edges;
 
     // mesh vertex index as key
     public static List<Vertex> FindSharedVertices(Vector3[] aVertices)
     {
         var list = new List<Vertex>();
         for (int i = 0; i < aVertices.Length; i++)
         {
             Vertex v = null;
             foreach(var item in list)
             {
                 if ((item.position - aVertices[i]).sqrMagnitude < 0.0001f)
                 {
                     v = item;
                     break;
                 }
             }
             if (v == null)
             {
                 v = new Vertex { position = aVertices[i] };
             }
             list.Add(v);
         }
         return list;
     }
     public static Dictionary<Edge, TrianglePair> CreateEdgeList(List<Vertex> aTriangles )
     {
         var res = new Dictionary<Edge, TrianglePair>();
         int count = aTriangles.Count / 3;
         for(int i = 0; i < count; i++)
         {
             Vertex v1 = aTriangles[i*3    ];
             Vertex v2 = aTriangles[i*3 + 1];
             Vertex v3 = aTriangles[i*3 + 2];
             TrianglePair p;
             Edge e;
             e = new Edge(v1, v2);
             if (!res.TryGetValue(e, out p))
             {
                 p = new TrianglePair();
                 res.Add(e, p);
             }
             p.Add(i);
             e = new Edge(v2, v3);
             if (!res.TryGetValue(e, out p))
             {
                 p = new TrianglePair();
                 res.Add(e, p);
             }
             p.Add(i);
             e = new Edge(v3, v1);
             if (!res.TryGetValue(e, out p))
             {
                 p = new TrianglePair();
                 res.Add(e, p);
             }
             p.Add(i);
         }
         return res;
     }
 
     public static List<int> GetNeighbors(Dictionary<Edge, TrianglePair> aEdgeList, List<Vertex> aTriangles)
     {
         var res = new List<int>();
         int count = aTriangles.Count / 3;
         for (int i = 0; i < count; i++)
         {
             Vertex v1 = aTriangles[i * 3    ];
             Vertex v2 = aTriangles[i * 3 + 1];
             Vertex v3 = aTriangles[i * 3 + 2];
             TrianglePair p;
             if (aEdgeList.TryGetValue(new Edge(v1, v2), out p))
             {
                 if (p.t1 == i)
                     res.Add(p.t2);
                 else
                     res.Add(p.t1);
             }
             else
                 res.Add(-1);
             if (aEdgeList.TryGetValue(new Edge(v2, v3), out p))
             {
                 if (p.t1 == i)
                     res.Add(p.t2);
                 else
                     res.Add(p.t1);
             }
             else
                 res.Add(-1);
             if (aEdgeList.TryGetValue(new Edge(v3, v1), out p))
             {
                 if (p.t1 == i)
                     res.Add(p.t2);
                 else
                     res.Add(p.t1);
             }
             else
                 res.Add(-1);
         }
         return res;
     }
     public static List<int> GetNeighbors(Mesh aMesh)
     {
         var vertexList = FindSharedVertices(aMesh.vertices);
         var tris = aMesh.triangles;
         var triangles = new List<Vertex>(tris.Length);
         foreach (var t in tris)
             triangles.Add(vertexList[t]);
         var edges = CreateEdgeList(triangles);
         return GetNeighbors(edges, triangles);
     }
 }

With this class you can simply use MeshTriangleNeighbors.GetNeighbors(mesh); to get a List with all the neighbor information. The returned List is designed similar to the triangles array, but instead of referencing vertices, each triple of numbers represent the 3 neighbor triangle indices for a triangle. Note that i did not store the first vertex index of the triangle, but the actual triangle index (first vertex index divided by 3). For example

 [0] : 2  // \
 [1] : 1  //   First triangle neighbors
 [2] : 3  // /
 [3] : 0  // \ 
 [4] : 4  //   Second triangle neighbors
 [5] : 6  // /
  ....

Since a mesh can not be closed (or if splitted vertices are too far apart so they aren't recognised as the same) it's possible that a triangle doesn't have 3 neighbors. If an edge of a triangle doesn't have a "partner", the index will be "-1". For example the default quad mesh in Unity (only two triangles) only has one shared edge. The result looks like this: [1,-1,-1,0,-1,-1] So the first triangle (index 0) has one neighbor (index 1) and the second triangle (index 1) has one neighbor (index 0). All other edges (the 4 borders of the quad) do not have a neighbor. When tested with the sphere, cube or capsule mesh every triangle has 3 neighbors as they are closed meshes.

Note that 0.0001f in the "FindSharedVertices" method determines when two or more vertices are considered "equal". In most cases splitted vertices should have exactly the same position. However in some cases there might be a small error. Note that this threshold is the squared distance, so the actual tolerance is 0.01

Keep in mind that calling "GetNeighbors" creates quite a bit of garbage when called. Though only the resulting List<int> is required in the end. You should use this method only once at start or you could even calculate the list at edit time and store it somewhere