Company wants to setup a HSA contribution (employer) based on # of years at the company.

For example: those with 5 years employment get $1000, 10 years $2000. Would this work inside of a 125 plan?

That's OK, as long as the contributions are made "through a cafeteria plan" and the contributions will not violate the cafeteria plan nondiscrimination rules which prohibit excess benefits to HCEs.

Employer contributions are made "through a cafeteria plan" by establishing a cafeteria plan and allowing employees to contribute to the HSA through it. The employer contributions will be treated this way even if the employee does not contribute their own money.