Since $F=ma$, the force should change if acceleration changes shouldn't it?
And since acceleration is the rate of change of velocity, can velocity be constant if acceleration changes?
I think you're confusing acceleration with velocity. If a body experiences a constant force, the value of acceleration is also constant, which means the value of velocity increases/decreases in a linear fashion, depending on whether the body is accelerating ($a>0$) or decelerating ($a<0$). If the force changes, the acceleration also changes, assuming constant mass. They're proportional vectors with mass as the proportionality factor.
Regarding the second part of your question: generally, if the value of acceleration isn't constant (in fact if it's not equal to zero), the velocity also changes.
If we consider vectors of acceleration and velocity, they don't have to be collinear at all (as witnessed by circular or general curvilinear motion) nor have the same orientation if they happen to be collinear (e.g. the deceleration vector ($a<0$) and current speed vector ($v>0$) of a body are oriented contrary to each other in 1D). For example: in circular motion, the vector always points to the center of rotation, but the value of acceleration may be variable or constant, which affects the speed: if the acceleration is of constant value, the speed is also constant, but the velocity vector changes all the time. If the centripetal acceleration has a value that is not constant (and the radius of the orbit remains the same), the speed is also variable.
If the force on a body is constant, it will accelerate uniformly. The velocity will be a linear function of time, and the position will be a quadratic function. This is a very common scenario with falling objects. For objects near the surface of the Earth, the force of gravity is very nearly constant. Without friction, a body will move along a parabolic path.
The velocity of a body can only be constant if the acceleration is zero, since the acceleration is the rate of change of the velocity. This is the scenario outlined in Newton's First Law, that a body in motion will continue to move with the same velocity if the force on it is zero.
The force and the velocity are both vectors with 3 components. An example of force, uniform by size but constantly changing direction, is as simple as a rotation, e.g. carrousel. The force is pointing towards the centre of rotation, while speed is rectangular to the force.
The short formula F = ma is in fact saying: If acceleration is constant by size and direction, then for a given mass the force is constant by size and direction.
For a free-falling object, the formula is useful only for a fraction of second or at most few seconds (depends on falling body and requested precison). Force changes from gravity-pull-only to reaction of air friction force. The latter changes from neglectible over linear to square law in second or two. Even if falling in a vacuum tube, in a minute or two, the gravity itself changes enough to notice.
To "reformulate the formula", students learn that d(vector F)= m × d(vector a) or even better, since force is reason for acceleration, d(vector a) = d(vector F) / m saying that (for a very short time of observation) size and direction of acceleration changes as much as size and direction of force divided by mass. And even that formula is not correct if mass changes during time, like launched rocket.