The question is, what do you mean by "force"? :)
I mean, what confuses you is probably:
Why do we call $$F=ma$$ a physical law, if this is the only definition of force?
This is a good thought. But fortunately Newton has not just this one axiom, but two (the historical "first" is a special case of $F=ma$, but there is a third), which are connected.
So I would put it like this:
If two bodies interact, we call this "exert a force on each other". The result is some change in motion (I will not question the concepts of space and time here, which are necessary for such a statement). And now comes the law (i.e. some nontrivial statement derived from experiment):
The ratio of the accelerations of the two bodies is always the same, and independent of the special type of interaction.
And more than that: this ratio is "transitive", in the sense that the ratio between the bodies A and C is the product of the ratios between A and B and B and C. This step is not self-evident, the ratio could also have been a property of the pair of bodies. But this transitivity allows us to assign a property to each body, that we call "mass".
You see how you need both, the actio=reactio and the acceleration to give those concepts a meaning...?
Well, this mass has no physical meaning so far, only the ratio of masses. We just call some arbitrarily chosen mass one kg.
And now that we know what to call mass, we can define a force by $F=ma$. The value of the force has no meaning at all so far, since we already defined mass with this very equation. To call this concept force gets a meaning later, if we add to this definition (concerning the action of the force) some further formulas about the cause of the force, like Hooke's law or the law of gravitation.
The issue with the relativistic velocities from your second paragraph,
I've learned even if we push some particle 'by constant force', the
particle's acceleration would be decreasing in time, instead of
maintaining some value.
is resolved from this viewpoint. "Constant force" now means, that the reaction on the object from which the force is applied is constant. So this statement says that in non-classical circumstances there are deviations from the abovementioned observation, that the ratio of accelerations depends only on the property "mass" of the two involved objects. But fortunately these deviations occur not randomly but systematically, and the system turns out to be: we can still retain all the above concepts with the addition, that the mass is dependent on the velocity. It's still transitive, so it's still a meaningfull concept. And derived from it, force is meaningfull...
(Actually, force is harder to retain as a concept, since it's not always possible to say, what pair of objects is interacting, you can have interaction with a field also... and then it's maybe better to let it go and use different descriptions of reality :))