So you're saying your pathfinding graph is about 150x150 (10000 pixels divided by 64 pixel grid cells)? Or that your graph is 10000x10000 with every single pixel set as node? Long-distance pathfinding can be slow even on a 150x150 graph, and on a 10K it would crawl no matter what. The longer the distance between start and destination, the more of the surroundings A* may need to explore due to obstacles. Part of the problem can also be 'pathfinding traps' or large areas that ultimately are discovered to be complete dead ends after A* has spent considerable amount of time exploring them.
To speed up large maps, one solution is hierarchical pathfinding. In it, you group up sets of grid nodes into supergroups and calculate their connections to similalry generated neighbours, creating a graph that represents their connections on a higher hierarchical level. You perform initial pathfinding on higher hierarchical level and resolve only the immediate group's nodes as an actual path to walk, then the next one after current one has been traversed, until the goal is reached. If the map is completely static, optimally this generation has been done beforehands and injected into the game as pathfinding graph that is immediately usable. On procgenned maps, you'd just have to generate the hierarchies during world generation.
Here for example is a grid map that has been grouped into 4x4 groups and their connections have been checked (taken from
this article):
And here's how it would look as a pathfinding graph for the higher hierarchy (from the same article):
The numbers are precalculated travel distances between the nodes. As can be seen, the hierarchic set forces one to consider a graph as what graphs really are, and understand that grid is just a special case.