I realize you might mean you're not sure how they're relevant to the topic at hand, rather than how they're relevant to each other. I'll attempt to illustrate this connection by providing the simplest possible internally-consistent model of an abstract system that appears to resemble reality as we experience it, including the passage of time. I will define the base components of the system, and compare the emergent interactions of these components with the phenomena we experience.

First, we observe that any given physical space can be said to represent some positive quantity of information; a physical space can thus represent the "state" of a system.

Second, we assume the existence of "causality", patterns for recognizing and amending portions of a state. We may then refer to a possible application of these patterns to a portion of a given state, which we'll call an "event".

For every pairing of initial state and set of possible events, there exists a space of computable states that we may call a "totality". A totality can be represented as a directed graph. The root of this graph is the initial state, edges are detected events from which new states can be computed, and child nodes represent states transformed by events.

Now, when we talk about "the passage of time", we mean the iterative computation of successive levels of totality. An event's distance from the root node is its chronological order, and thus a "point in time" is a depth in the graph of totality. The full state of the system at a given point in time is then naturally the union of the state nodes at that depth.

Our experience of the passage of time is represented similarly in the brain, with neurons building complex models by generating successive branching layers. We hinge knowledge on key experiences, and we perceive time fractally, in heirarchical levels of detail. It seems intuitive that our brains, which function by reflecting our outward reality internally, would in fact structurally reflect reality. Furthermore, the conclusion that the causality graph becomes more dense as mass in a space grows more dense seems to reflect general relativity.

Here's where Gödel and Turing come in. A totality is defined iteratively: there is no way to know its complete value except to evaluate its events, and the only thing to do with it is evaluate its events according to its patterns of causality. Similarly, given a Turing machine (or a consistent system of axioms), there's no way to know the final state (or final set of conclusions) except to run it with some input, and the only thing it can do is run.

So back to the question:

> what is time, physically, and why should it have to exist as some sort of a physical process in the first place

Time, physically, is the continuous evaluation of possible states of a physical space (like ours). It has to exist because it is, by definition (to the point of tautology), the only thing that can possibly happen. It is still a "mathematical construct", but only to the degree that we also are ¯\_(ツ)_/¯