Seems like a trivial problem to me.

If the graph is directed, do an SCC decomposition in linear time using a graph library and then any SCC with size more than one has at least a loop, trivially extracted by following any edges in the SCC.

If the graph is undirected, compute a spanning tree in linear time using a graph library and then any edge outside the tree forms a loop, again trivially extractable from the edge and the paths from its endpoints to their least common ancestor in the tree.

Since those algorithms are already asymptotically optimal, it's just an engineering problem of finding the solution with the best constant factor given the precise data structures and goal in question.